Минимальное количество ребер, которые нужно удалить из данного графа, чтобы между заданными парами вершин не существовало пути.
Дан неориентированный граф, состоящий из N со значениями в диапазоне [1, N] такой, что вершины (i, i + 1) связаны, и массив arr[] , состоящий из M пар целых чисел, задача состоит в том, чтобы найти минимальное количество ребра, которые должны быть удалены из графа так, чтобы не существовало никакого пути для каждой пары (u, v) в массиве arr[] .
Примеры:
Input: arr[] = {{1, 4}, {2, 5}
Output: 1
Explanation:
For N = 5, the given graph can be represented as:1 <-> 2 <-> 3 <-> 4 <-> 5
After removing the edge between vertices 2 and 3 or the edge between vertices 3 and 4, the graph modifies to:
1 <-> 2 3 <-> 4 <-> 5
Now, there doesn’t exist any path between every pair of nodes in the array. Therefore, the minimum number of edges that should be removed is 1.
Input: arr[] = {{1, 8}, {2, 7}, {3, 5}, {4, 6}, {7, 9}}
Output: 2
Подход: Данная проблема может быть решена с использованием жадного подхода. Идея состоит в том, чтобы отсортировать заданный массив пар arr[] в порядке возрастания конечных пар и для каждой пары, скажем (u, v), удалить ближайшие ребра, связанные с вершиной v , так, чтобы все остальные вершины на связных компонентах, содержащих вершина v недостижима. Выполните следующие шаги, чтобы решить данную проблему:
- Создайте переменную, скажем, minEdges как 0 , которая хранит количество удаленных ребер.
- Создайте переменную, достижимую как 0 , которая отслеживает наименьшую вершину, достижимую из последней вершины, т. е. N .
- Отсортируйте заданный массив пар arr[] в порядке возрастания второго значения пар.
- Пройдите по заданному массиву arr[] и для каждой пары (u, v) в arr[] , если достижимо > u , это означает, что не существует пути между u и v , в противном случае удаляется последнее ребро между (v – 1) и v — самый оптимальный выбор. Следовательно, увеличьте значение minEdges на 1 , и значениеreachable будет равно v .
- После выполнения вышеуказанных шагов выведите в качестве результата значение minEdges .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(M*log M)
Вспомогательное пространство: O(1)