P3388 【模板】割点（割顶）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int cntdfs, dfs[MAXnd + 10], low[MAXnd + 10];
int cntcut; bitset<MAXnd + 10> iscut;
void Tarjan(int cur, int root) {
    dfs[cur] = low[cur] = ++cntdfs;
    int times = 0; bool havcnt = 0;
    for (int i = head[cur]; i; i = nex[i]) {
        if (dfs[to[i]]) {
            low[cur] = min(low[cur], dfs[to[i]]);
        } else {
            Tarjan(to[i], root);
            low[cur] = min(low[cur], low[to[i]]);
            if (!havcnt) {
                if (low[to[i]] >= dfs[cur]) {
                    ++times;
                    if (cur != root || times >= 2) {
                        havcnt = 1;
                        ++cntcut;
                        iscut[cur] = 1;
                    }
                }
            }
        }
    }
}

signed main() {
    // ......
    for (int i = 1; i <= n; ++i) {
        if (!dfs[i]) {
            Tarjan(i, i);
        }
    }
}

T103492 【模板】点双连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int cntdfs, dfs[MAXnd + 10], low[MAXnd + 10];
int cntdcc; vector<int> dcc[MAXnd + 10];
int top, stk[MAXnd + 10];
void Tarjan(int cur) {
    dfs[cur] = low[cur] = ++cntdfs;
    if (!head[cur]) {
        dcc[++cntdcc].push_back(cur);
        return;
    }
    stk[++top] = cur;
    for (int i = head[cur]; i; i = nex[i]) {
        if (dfs[to[i]]) {
            low[cur] = min(low[cur], dfs[to[i]]);
        } else {
            Tarjan(to[i]);
            low[cur] = min(low[cur], low[to[i]]);
            if (low[to[i]] >= dfs[cur]) {
                ++cntdcc;
                int x;
                do {
                    x = stk[top--];
                    dcc[cntdcc].push_back(x);
                } while (x != to[i]);
                dcc[cntdcc].push_back(cur);
            }
        }
    }
}

signed main() {
    // ......
    for (int i = 1; i <= n; ++i) {
        if (!dfs[i]) {
            Tarjan(i);
        }
    }
}