割点

https://www.cnblogs.com/collectionne/p/6847240.html

关于为什么low[u]=min(low[u],dfn[v]);不能写成low[u]=min(low[u],low[v]);

最好的反例在这里:

不难发现4号节点本是一个割点，但若写为low[u]=min(low[u],low[v]);

则它的儿子5号节点，会因为7号节点翻过头，使low[7]=1;

然而其实low[7]应是为4的，这样，4号节点就会因为儿子节点的low值没有大于它的dfn，而被判为割点了

#include<bits/stdc++.h>
using namespace std;
struct{
    int to;
    int ne;
}a[200005];
int num,head[20004],Dfn,dfn[20004],low[20004];
bool b[20004];
void lian(int from,int to){
    num++;
    a[num].to=to;
    a[num].ne=head[from];
    head[from]=num;
}
void  tarjan(int u,int fa){
    int i,child=0;
    dfn[u]=low[u]=++Dfn;
    for(i=head[u];i;i=a[i].ne){
        if(!dfn[a[i].to]){
            child++;
            tarjan(a[i].to,fa);
            low[u]=min(low[u],low[a[i].to]);
            if(low[a[i].to]>=dfn[u]&&u!=fa)
                b[u]=1;
        }
        low[u]=min(low[u],dfn[a[i].to]);
    }
    if(child>=2&&u==fa)b[u]=1;
}
int main(){
    int n,m,i,j,u,v,sum=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        lian(u,v);
        lian(v,u);
    }
    for(i=1;i<=n;i++)
        tarjan(i,i);
    for(i=1;i<=n;i++)
        if(b[i])sum++;
    printf("%d
",sum);
    for(i=1;i<=n;i++)
        if(b[i])printf("%d ",i);
    return 0;
}