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
     
       2 #include
      
        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\n", tot);50     for(int i = 1; i <= n; i++) 51         if(cut[i]) printf("%d ", i);52     return 0;53 }
      
     

我觉得比缩点好懂QAQ