Определение. Мостом называется ребро, при удалении которого связный неориентированный граф становится несвязным.
Определение. Точкой сочленения называется вершина, при удалении которой связный неориентированный граф становится несвязным.
Пример задачи, где их интересно искать: дана топология сети (компьютеры и физические соединения между ними) и требуется установить все единые точки отказа — узлы и связи, без которых будут существовать два узла, между которыми не будет пути.
Наивный алгоритм поочередного удаления каждого ребра $(u, v)$ и проверки наличия пути $u \leadsto v$ потребует $O(m^2)$ операций. Чтобы научиться находить мосты быстрее, сначала сформулируем несколько утверждений, связанных с обходом в глубину.
Запустим DFS из произвольной вершины. Введем новые виды рёбер:
Прямые рёбра — те, по которым были переходы в dfs.
Обратные рёбра — то, по которым не было переходов в dfs.
Заметим, что никакое обратное ребро $(u, v)$ не может являться мостом: если его удалить, то всё равно будет существовать какой-то путь от $u$ до $v$, потому что подграф из прямых рёбер является связным деревом.
Значит, остается только проверить все прямые рёбра. Это уже немного лучше — такой алгоритм будет работать за $O(n m)$.
Соптимизировать его до линейного времени (до одного прохода dfs) поможет замечание о том, что обратные рёбра могут вести только «вверх» — к какому-то предку в дереве обхода графа, но не в другие «ветки» — иначе бы dfs увидел это ребро раньше, и оно было бы прямым, а не обратным.
Тогда, чтобы определить, является ли прямое ребро $v \to u$ мостом, мы можем воспользоваться следующим критерием: глубина $h_v$ вершины $v$ меньше, чем минимальная глубина всех вершин, соединенных обратным ребром с какой-либо вершиной из поддерева $u$.
Для ясности, обозначим эту величину как $d_u$, которую можно считать во время обхода по следующей формуле:
$$ d_v = \min \begin{cases} h_v, &\\ d_u, &\text{ребро } (v \to u) \text{ прямое} \\ h_u, &\text{ребро } (v \to u) \text{ обратное} \end{cases} $$Если это условие ($h_v < d_u$) не выполняется, то существует какой-то путь из $u$ в какого-то предка $v$ или саму $v$, не использующий ребро $(v, u)$, а в противном случае — наоборот.
const int maxn = 1e5;
bool used[maxn];
int h[maxn], d[maxn];
void dfs(int v, int p = -1) {
used[v] = true;
d[v] = h[v] = (p == -1 ? 0 : h[p] + 1);
for (int u : g[v]) {
if (u != p) {
if (used[u]) // если ребро обратное
d[v] = min(d[v], h[u]);
else { // если ребро прямое
dfs(u, v);
d[v] = min(d[v], d[u]);
if (h[v] < d[u]) {
// если нельзя другим путем добраться в v или выше,
// то ребро (v, u) -- мост
}
}
}
}
}
Примечание. Более известен алгоритм, вместо глубин вершин использующий их $tin$, но автор считает его чуть более сложным для понимания.
#Точки сочленения
Задача поиска точек сочленения не сильно отличается от задачи поиска мостов.
Вершина $v$ является точкой сочленения, когда из какого-то её ребёнка $u$ нельзя дойти до её предка, не используя ребро $(v, u)$. Для конкретного прямого ребра $v \to u$ этот факт можно проверить так: $h_v \leq d_u$ (теперь неравенство нестрогое, так как если из вершины можно добраться только до нее самой, то она все равно будет точкой сочленения).
Используя этот факт, можно оставить алгоритм практически прежним — нужно проверить этот критерий для всех прямых рёбер $v \to u$:
void dfs(int v, int p = -1) {
used[v] = 1;
d[v] = h[v] = (p == -1 ? 0 : h[p] + 1);
int children = 0;
for (int u : g[v]) {
if (u != p) {
if (used[u])
d[v] = min(d[v], h[u]);
else {
dfs(u, v);
d[v] = min(d[v], d[u]);
if (h[v] <= d[u] && p != -1) { // корень (p == -1) обрабатываем отдельно
// v -- точка сочленения
// (это условие может выполниться много раз для разных детей)
}
children++;
}
}
}
if (p == -1 && children > 1) {
// v -- корень и точка сочленения
}
}
Единственный крайний случай — это корень, так как в него мы по определению войдём раньше других вершин. Но фикс здесь очень простой — достаточно посмотреть, было ли у него более одной ветви в обходе (если корень удалить, то его поддеревья станут несвязными между собой).