【学习/模板】tarjan割点

P3388 【模板】割点（割顶）

tarjan爷爷造福世界

割点适用于无向图，所以low数组定义发生变化，不再是最早能追溯到的栈中节点编号（因为是无向边，没有意义），而是一直往下走能绕到的最早的割点编号
在tarjan求强连通分量是low[u] = min(low[u], dfn[v]) 与 low[u] = min(low[u], low[v]) 等价但在求割点时只能用前面的qwq
原因：在求强连通分量时，如果v已经在栈中，那么说明u，v一定在同一个强连通分量中，所以到最后low[u]=low[v]是必然的，提前更新也不会有问题；

代码qwq

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int maxn = 20020, maxm = 100010;
 5 int n, m, num = 0, tim = 0, tot = 0;
 6 int head[maxm], dfn[maxn], low[maxn];
 7 bool cut[maxn];
 8 struct edge {
 9     int nxt, to;
10 }e[maxm<<1];
11 int read() {
12     char ch = getchar(); int x = 0, f = 1;
13     while(ch<'0'||ch>'9') {if(ch == '-') f = -1; ch = getchar();}
14     while(ch>='0'&&ch<='9') {x = x * 10 + ch - '0'; ch = getchar();}
15     return x * f;
16 }
17 void add(int from, int to) {
18     e[++num].nxt = head[from];
19     e[num].to = to;
20     head[from] = num;
21 }
22 void tarjan(int u, int fa) {
23     dfn[u] = low[u] = ++tim;
24     int child = 0;
25     for(int i = head[u]; i; i = e[i].nxt) {
26         int v = e[i].to;
27         if(!dfn[v]) {
28             tarjan(v, fa);
29             low[u] = min(low[u], low[v]);
30             if(low[v] >= dfn[u] && u != fa) cut[u] = 1;
31             //不为根节点， 则对于边(u, v) ，如果low[v]>=dfn[u]，此时u就是割点 
32             if(u == fa) child++;
33         }
34         low[u] = min(low[u], dfn[v]);/**/ 
35     }
36     if(child >= 2 && u == fa) cut[u] = 1;
37     //如果是根节点 ， 有两棵及以上的子树， 即为割点 
38 }
39 int main() {
40     scanf("%d%d", &n, &m);
41     for(int i = 1; i <= m; i++) {
42         int x = read(), y = read();
43         add(x, y), add(y, x);
44     }
45     for(int i = 1; i <= n; i++) 
46         if(!dfn[i]) tarjan(i, i);
47     for(int i = 1; i <= n; i++) 
48         if(cut[i]) tot++;
49     printf("%d
", tot);
50     for(int i = 1; i <= n; i++) 
51         if(cut[i]) printf("%d ", i);
52     return 0;
53 }

我觉得比缩点好懂QAQ