Минимальное количество ребер, которые необходимо удалить из заданного неориентированного графа, чтобы удалить любой существующий путь между узлами A и B.

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

Даны два целых числа N и M , обозначающие количество вершин и ребер в графе, и массив ребер[][] размера M , обозначающий ребро между ребрами[i][0] и ребрами[i][1] , задача состоит в следующем: найти минимальные ребра, непосредственно связанные с узлом B , которые необходимо удалить так, чтобы между вершинами A и B не существовало пути.

Примеры:

Input: N = 4, A = 3, B = 2, edges[][] = {{3, 1}, {3, 4}, {1, 2}, {4, 2}}
Output: 2
Explanation: The edges at index 2 and 3 i.e., {1, 2} and {4, 2} must be removed as they both are in the path from vertex A to vertex B.

Input: N = 6, A = 1, B = 6, edges[][] = {{1, 2}, {1, 6}, {2, 6}, {1, 4}, {4, 6}, {4, 3}, {2, 4}}
Output: 3

Подход: Данная проблема может быть решена с использованием алгоритма поиска в глубину. Можно заметить, что все ребра, связанные с конечной вершиной B и существующие на любом пути от начальной вершины A до конечной вершины B , должны быть удалены. Следовательно, выполните поиск в глубину , начиная с узла A , и сохраните все посещенные вершины из него. Выполните следующие шаги, чтобы решить проблему:

  • Создайте матрицу смежности g[][] , в которой хранятся ребра между двумя узлами.
  • Инициализируйте массив v[] , чтобы отметить узел, до которого можно добраться из узла A .
  • Создайте переменную cnt , в которой хранится количество узлов, которые необходимо удалить. Первоначально cnt = 0 .
  • Перебрать все узлы и, если он достижим из A и напрямую связан с B , увеличить значение cnt .
  • Значение, хранящееся в cnt , является требуемым ответом.

Ниже приведена реализация вышеуказанного подхода:

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

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