Точки сочленения: почему у корня DFS особое условие (два и более ребёнка)?

Вершина v (не корень) — точка сочленения, если у неё есть ребёнок u в дереве DFS, из поддерева которого нельзя добраться выше v: low[u] >= tin[v]. Тогда удаление v отрезает это поддерево.

Почему корень особый. У не-корня всегда есть «верх» (предки), и условие low[u] >= tin[v] означает «поддерево u связано с остальным графом только через v». Но у корня нет предков — единственный способ, которым его поддеревья связаны между собой, это сам корень. Если у корня в дереве DFS ≥ 2 детей, эти поддеревья не связаны напрямую (иначе DFS объединил бы их в одно поддерево, добравшись по ребру), значит удаление корня их разъединит — корень точка сочленения. Если ребёнок один — удаление корня оставляет граф связным.

int timer = 0;
vector<int> tin, low;
vector<bool> isCut;
vector<int> g[N];

void dfs(int v, int parent) {
    tin[v] = low[v] = timer++;
    int children = 0;
    for (int u : g[v]) {
        if (u == parent) continue;          // здесь хватает вершины (см. ниже про кратные)
        if (tin[u] != -1) {
            low[v] = min(low[v], tin[u]);
        } else {
            dfs(u, v);
            low[v] = min(low[v], low[u]);
            if (parent != -1 && low[u] >= tin[v]) isCut[v] = true; // не-корень
            children++;
        }
    }
    if (parent == -1 && children >= 2) isCut[v] = true;            // корень
}

Сложность O(V+E), память O(V). Обратите внимание: для не-корня условие нестрогое >= (в отличие от мостов, где строгое >), потому что вершина-сочленение может сама лежать на цикле и всё равно резать граф.