有向图强连通分量，缩点

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
// tarjan 缩点
void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk.push(u); in_stk[u] = 1;

    for (int y : g[u]) {
        if (!dfn[y]) {
            tarjan(y);
            low[u] = min(low[u], low[y]);
        } else if(in_stk[y]) low[u] = min(low[u], dfn[y]);
    }
    
    if (dfn[u] == low[u]) {
    	int y;
    	++scc_cnt;
    	do {
    		y = stk.top();
    		w[scc_cnt] += a[y];
    		stk.pop();
    		in_stk[y] = 0;
    		id[y] = scc_cnt;
		}while(y != u);
	}
}
// tarjan 缩点后，重新建图
for (int i = 1; i <= n; i++) {
	for (int j : g[i]) {
		if (id[i] != id[j]) {
			gg[id[i]].push_back(id[j]);
			in[id[j]]++;
		}
	}
}

割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    int cnt = 0;
    for (int j : g[u]) {
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
            if (low[j] >= dfn[u]) {
                cnt ++;
                if(u != root || cnt > 1) cut[u] = true;
            }
        }
        else low[u] = min(low[u], dfn[j]);
    }
}

割边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void tarjan(int x, int in_edge)
{
    dfn[x] = low[x] = ++ timestamp;
    for (int i = head[x]; i; i = nt[i]) {
		int y = ver[i];
		if (i == (in_edge ^ 1)) continue;
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] > dfn[x]) {
				brige[i] = brige[i ^ 1] = true;
            }
        }
        else low[x] = min(low[x], dfn[y]);
    }
}

点双缩点

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
void tarjan(int x) {
	dfn[x] = low[x] = ++timestamp;
	stk.push(x);
	if (x == root && head[x] == 0) { //孤立点
		dcc[++cnt].push_back(x);
		return;
	}

	int flag = 0;
	for (int y : ng[x]) {
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
			if (low[y] >= dfn[x]) {
				flag ++;
				cnt++;
				if (x != root || flag > 1) cut[x] = 1;
				int z;
				do {
					z = stk.top();
					stk.pop();
					dcc[cnt].push_back(z);
				}while(z != y);
				dcc[cnt].push_back(x);
			}
		} else low[x] = min(low[x], dfn[y]);
	}
}
// 缩点
num = cnt;
for (int i = 1; i <= n; i++) 
	if (cut[i]) new_id[i] = ++num;

for (int i = 1; i <= cnt; i++) 
	for (int j = 0; j < dcc[i].size(); j++) {
		int x = dcc[i][j];
		if (cut[x]) {
			add_c(i, new_id[x]);
			add_c(new_id[x], i);
		}
	}

边双

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void tarjan(int x, int to) {
	dfn[x] = low[x] = ++timestamp;

	for (int i = head[x]; i; i = nt[i]) {
		int y = ver[i];
		if (i == (to ^ 1)) continue;
		if (!dfn[y]) {
			tarjan(y, i);
			low[x] = min(low[y], low[x]);
		} else low[x] = min(low[x], dfn[y]);
		if (low[y] > dfn[x]) brige[i] = brige[i ^ 1] = 1, ans++;
	}
}
void dfs(int x, int fa) {
	id[x] = num;
	po[num].push_back(x);
	for (int i = head[x]; i; i = nt[i]) {
		int y = ver[i];
		if (id[y]) continue;
		if (brige[i]) continue;
		dfs(y, x);
	}
}

练习题

题目 类型
Non-academic Problem 割边板子题
网络 边双
【模板】割点（割顶） 割点模板
BLO-Blockade 点双
Knights of the Round Table 点双