Как решить эту проблему подключения графа?

Question

Недавно я столкнулся с нижеуказанным вопросом в интервью, на который я не смог ответить. Может кто-нибудь помочь мне найти алгоритм для его решения? Какую графовую концепцию мне следует применить для ее решения?

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

Ввод: 6,5 (где 6 - это число маршрутизаторов, а 5 - количество ссылок) [(1,2), (2,3), (3,4), (4,5), (6,3)]

Выход: ожидаемое возвращаемое значение 2 3 4

Answer 1

Эта проблема, по сути, сводится к нахождению всех точек сочленения графика. Точка сочленения в графе - это узел, который, если удалить его, отключает граф, и это именно то, что вы ищете.

Это хорошо изученная проблема, которая имеет хорошее решение с использованием глубины в первую очередь. поиск. Надеюсь, это даст вам правильные условия для поиска!

Answer 2

Ваш график - это граф G {"1" - "2" "2" - "3" "3" - "4" "4" - "5" "6" - "3"} в GraphViz , который генерирует

, поэтому {2, 3, 4} являются узлами с более чем одним отдельным ребром.

Если на входе гарантированно не будет повторяющихся ребер, то потребуется любой узел, который появляется во входных данных более одного раза.

Если на входе не гарантировано, что на ребрах нет дубликатов, у вас есть подсчитать разные ребра для каждого узла и выбрать узлы, которые не имеют только одного ребра.