Мосты и точки сочленения

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

Мост — это ребро, удаление которого увеличивает количество связных компонент. Оно является единственным путём между двумя областями графа.

Точка сочленения — это вершина, удаление которой нарушает связность графа. В сетях такие единственные точки отказа особенно опасны.

Оба алгоритма выполняются за один DFS, отслеживая время обнаружения и значение low, подобно алгоритму Тарьяна, но для неориентированного графа.

Значение low вершины — это самый ранний идентификатор обнаружения, достижимый из её поддерева DFS, возможно через одно обратное ребро вверх.

Когда DFS входит в вершину, установите её disc и low равными значению текущего таймера и переходите к её соседям.

После рекурсивной обработки потомка v, если low[v] > disc[u], ни одно обратное ребро не проходит выше u, поэтому ребро u-v является мостом.

Не являющаяся корнем вершина u — точка сочленения, если для потомка v выполняется low[v] >= disc[u]: поддерево v не может обойти u.

Корень DFS является точкой сочленения только тогда, когда у него два или более потомка в дереве DFS, поэтому подсчитайте их.

При обновлении low по обратному ребру не возвращайтесь по ребру к родителю, иначе неправильно определите мосты.

Один DFS одновременно находит все мосты и точки сочленения за O(V + E). Дополнительный обход не нужен.

После рекурсивной обработки потомка v из u вы обнаружили условие low[v] > disc[u]. Что вы нашли?

Один DFS с disc и low находит всё: low[v] > disc[u] означает мост, а low[v] >= disc[u] — точку сочленения. 🌉