Генерировать лексикографически наименьшую перестановку от 1 до N, где элементы следуют заданному отношению

Опубликовано: 19 Сентября, 2022

Учитывая целое число N и массив arr[] из M пар типа ( A i , Bi ), задача состоит в том, чтобы сгенерировать лексикографически наименьшую возможную перестановку от 1 до N , такую, что каждая A i встречается перед каждой B i .

Примеры:

Input: N = 4, arr[] = { {2, 1}, {3, 4}, {2, 4} }
Output: 2 1 3 4
Explanation: The following five permutations P satisfy the condition: 
(2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 2, 4, 1). 
The lexicographically smallest among them is (2, 1, 3, 4).

Input: N = 2, arr[] = { {2, 1} }
Output: 2 1

Подход: Задача может быть решена с использованием концепции графа, основанной на следующей идее:

Consider a N vertex graph where there is an directed edge from A to B if A occurs before B in the permutation.

  • So the target is to find a ordering such that any vertex occurs in the permutation after all its predecessors (the vertices which have edges directed to this one) have occurred in the permutation. 
  • While doing so, move from the least value to the maximum possible value for getting the lexicographically smallest permutation.

This can be done with the help of topological sorting.

  • The topological sort will start from the vertices having indegree 0 and in sequence of smaller to greater value.
  • After the topological sorting is over, if any vertex is still not included in the permutation, then no such permutation is possible.

Выполните следующие шаги, чтобы решить проблему:

  • Инициализировать один вектор (скажем, ответ ) для сохранения полученной перестановки.
  • Посетите M пар и создайте направленные ребра от первого значения arr[i] до второго значения arr[i] . Кроме того, увеличьте степень вхождения второго значения arr[i] на 1 .
  • Теперь найдите все элементы со степенью вхождения 0 , поместите их в результирующую перестановку в порядке возрастания и начните топологическую сортировку .
    • Добавьте любую вершину к перестановке, когда ее степень вхождения станет равной 0 .
    • При этом сохраняйте лексикографический порядок, т. е. двигайтесь от меньшего значения к большему.
  • Воспользуйтесь помощью min heap для выполнения топологической сортировки:
    • Первоначально держите вершины со степенью вхождения 0 в куче.
    • Затем извлеките вершину с наименьшим значением, добавьте ее к ans , удалите все ее ребра и уменьшите степень вхождения на 1 всех связанных с ней вершин.
    • Если в этом процессе степень вхождения какой-либо вершины становится равной 0, поместите ее в кучу.
  • Возвратите ans как последнюю требуемую перестановку.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ