洛谷3388：【模板】割点（割顶）—

洛谷3388：【模板】割点（割顶）——题解

阅读量：6657 次

发布时间：2019-06-25

本文共 1394 字，大约阅读时间需要 4 分钟。

给出一个n个点，m条边的无向图，求图的割点。

割点板子题，存一下一个可读板子。

（我发现当年的自己太naive了于是对着大神重新改了一下我的板子。）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int N=1e5+5;inline int read(){ int x=0,w=1;char ch=0; while(ch<'0'||ch>'9'){ if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*w;}struct node{ int to,nxt;}edge[N*2];int head[N],cnt,n,m,rtson;int dfn[N],low[N],t;bool cut[N];inline int add(int u,int v){ edge[++cnt].to=v;edge[cnt].nxt=head[u];head[u]=cnt;}void tarjan(int u,int f){ dfn[u]=low[u]=++t; for(int i=head[u];i;i=edge[i].nxt){ int v=edge[i].to; if(!dfn[v]){ tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]&&f)cut[u]=1; if(!f)rtson++; }else if(f!=v){ low[u]=min(low[u],dfn[v]); } } if(!f&&rtson>=2)cut[u]=1;}int main(){ n=read(),m=read(); for(int i=1;i<=m;i++){ int u=read(),v=read(); add(u,v);add(v,u); } for(int i=1;i<=n;i++) if(!dfn[i]){ rtson=0; tarjan(i,0); } int ans=0; 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); puts(""); return 0;}