Поиск точек сочленения

Определение. Точкой сочленения называется врешина, при удалении которой связный неориентированный граф становится несвязным.

Задача поиска точек сочленения не сильно отличается от задачи поиска мостов.

Вершина \(v\) является точкой сочленения, когда из какого-то её ребёнка \(u\) нельзя дойти до её предка, не используя ребро \((v, u)\). Для конкретного прямого ребра \(v \to u\) этот факт можно проверить так\[h_v \leq d_u\] (теперь нам нам достаточно нестрогого неравенства, так как если из вершины можно добраться до нее самой, то она все равно будет точкой сочленения).

Используя этот факт, можно оставить алгоритм практически прежним — нужно проверить этот критерий для всех прямых рёбер \(v \to u\):

void dfs(int v, int p = -1) {
    used[u] = 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) {
                    // v -- точка сочленения
                }
                children++;
            }
        }
    }
    if (p == -1 && children > 1) {
        // v -- корень и точка сочленения
    }
}

Единственный крайний случай — это корень, так как в него мы по определению войдём раньше других вершин. Но фикс здесь очень простой — достаточно посмотреть, было ли у него более одной ветви в обходе (если корень удалить, то эти поддеревья станут несвязными между собой).