B3609 [图论与代数结构 701] 强连通分量

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
int cntdfs, dfs[MAXnd + 10], low[MAXnd + 10];
int cntscc; vector<int> scc[MAXnd + 10];
int top, stk[MAXnd + 10]; bool instk[MAXnd + 10];
void Tarjan(int cur) {
    dfs[cur] = low[cur] = ++cntdfs;
    stk[++top] = cur; instk[cur] = 1;
    for (int i = head[cur]; i; i = nex[i]) {
        if (dfs[to[i]] && instk[to[i]]) {
            low[cur] = min(low[cur], dfs[to[i]]);
        } else if (!dfs[to[i]]) {
            Tarjan(to[i]);
            low[cur] = min(low[cur], low[to[i]]);
        }
    }
    if (dfs[cur] == low[cur]) {
        int x;
        ++cntscc;
        do {
            x = stk[top--]; instk[x] = 0;
            scc[cntscc].push_back(x);
        } while (x != cur);
    }
}

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

缩点：

1
2
3
4
5
for (int i = 1; i <= m; ++i) {
    if (inscc[from1[i]] != inscc[to1[i]]) {
        Insert2(inscc[from1[i]], inscc[to1[i]]);
    }
}