题解 P3388 【【模板】割点（割顶）】

关于tarjan算法，一直有一个很大的争议，就是low[u]=min(low[u],dfn[v]);

这句话，如果改成low[u]=min(low[u],low[v])就会wa掉，但是在求强连通分量时却没有问题

根据许多大佬的观点，我想提出自己的一点看法，在求强连通分量时，如果v已经在栈中，那么说明u，v一定在同一个强连通分量中，所以到最后low[u]=low[v]是必然的，提前更新也不会有问题，但是在求割点时，low的定义有了小小的变化，不再是最早能追溯到的祖先，（因为是个无向图）没有意义，应该是最早能绕到的割点，为什么用绕到，是因为是无向边，所以有另一条路可以走，如果把dfn[v]改掉就会上翻过头，可能翻进另一个环中，所以wa掉，仅是本人的一些个人看法，不知道讲的对不对，请各位指教。

下面附上ac代码

#include<cstdio>
#include<algorithm>
#define N (1000000+10)
using namespace std;
int a[N],nxt[N],head[N],dfn[N],low[N],cnt,k;
bool cut[N],bst[N];
void add(int x,int y){
    a[++k]=y; nxt[k]=head[x]; head[x]=k;
}
void tarjan(int u,int mr){
    int rc=0;
    dfn[u]=low[u]=++cnt;
    for (int p=head[u];p;p=nxt[p]){
        int v=a[p];
        if (!dfn[v]){
            tarjan(v,mr);
            low[u]=min(low[u],low[v]);
            if (low[v]>=dfn[u]&&u!=mr) cut[u]=true;
            if (u==mr) rc++;
        }
        low[u]=min(low[u],dfn[v]);
    }    
    if (u==mr&&rc>=2) cut[mr]=true;
}
int main(){
    int n,m,ans=0;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for (int i=1;i<=n;i++){
        if (!dfn[i]) tarjan(i,i);
    }
    //for (int i=1;i<=n;i++) printf("%d %d %d\n",i,dfn[i],low[i]);
    for (int i=1;i<=n;i++) if (cut[i]) ans++;
    printf("%d\n",ans);
    for (int i=1;i<=n;i++) if (cut[i]) printf("%d ",i);
}