T103481 【模板】割边

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
int cntdfs, dfs[MAXnd + 10], low[MAXnd + 10];
int cntcut; bitset<MAXeg * 2 + 10> iscut;
void Tarjan(int cur, int fromedge) {
    dfs[cur] = low[cur] = ++cntdfs;
    for (int i = head[cur]; i; i = nex[i]) {
        if (i == (fromedge ^ 1)) continue;
        if (dfs[to[i]]) {
            low[cur] = min(low[cur], dfs[to[i]]);
        } else {
            Tarjan(to[i], i);
            low[cur] = min(low[cur], low[to[i]]);
            if (low[to[i]] > dfs[cur]) {
                ++cntcut;
                iscut[i] = iscut[i ^ 1] = 1;
            }
        }
    }
}

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

T103489 【模板】边双连通分量

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
38
39
40
41
int cntdfs, dfs[MAXnd + 10], low[MAXnd + 10];
int cntcut; bitset<MAXeg * 2 + 10> iscut;
void Tarjan(int cur, int fromedge) {
    dfs[cur] = low[cur] = ++cntdfs;
    for (int i = head[cur]; i; i = nex[i]) {
        if (i == (fromedge ^ 1)) continue;
        if (dfs[to[i]]) {
            low[cur] = min(low[cur], dfs[to[i]]);
        } else {
            Tarjan(to[i], i);
            low[cur] = min(low[cur], low[to[i]]);
            if (low[to[i]] > dfs[cur]) {
                ++cntcut;
                iscut[i] = iscut[i ^ 1] = 1;
            }
        }
    }
}
int cntdcc, indcc[MAXnd + 10];
void EvaDcc(int cur) {
    indcc[cur] = cntdcc;
    for (int i = head[cur]; i; i = nex[i]) {
        if (indcc[to[i]] || iscut[i]) continue;
        EvaDcc(to[i]);
    }
}

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

如果只让输出边双的个数，桥数+不连通的图数也是正确答案。