【洛谷P3388】(模板)割点

【模板】割点

割点集合：一个顶点集合V，删除该集合的所有定点以及与这些顶点相连的边后，原图不连通，就称集合V为割点集合

点连通度：最小割点集合中的顶点数

边连通度：最小割边集合中的边数

割点：割点集合中唯一的一个元素

Tarjan求缩点：

一个点为缩点的条件：

1.该点为根，搜索树中有大于1个子树

2.该点u不为根，存在儿子v，dfn[u]>low[v]

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 #define N 100010

 #define M 200010

 int n,m,dfn[N],low[N];

 int head[N],num,root,cnt;

 bool gd[N];

 inline int read(){

     int x=; char c=getchar();

     while(c<''||c>'') c=getchar();

     while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }

     return x;

 }

 struct NODE{

     int to,next;

 } e[M];

 inline void add(int x,int y){

     e[++num].to=y;

     e[num].next=head[x];

     head[x]=num;

 }

 void Tarjan(int u){

     dfn[u]=low[u]=++cnt;

     int tot=;

     for(int i=head[u];i;i=e[i].next)

      if(!dfn[e[i].to]){

          tot++;

          Tarjan(e[i].to);

          low[u]=min(low[u],low[e[i].to]);

          if((u==root&&tot>)||(u!=root&&dfn[u]<=low[e[i].to]))

            gd[u]=;

      }

      else

       low[u]=min(low[u],dfn[e[i].to]);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     int x,y;

     for(int i=;i<=m;i++){

         x=read(); y=read();

         add(x,y); add(y,x);

     }

     for(int i=;i<=n;i++)

      if(!dfn[i]){

         root=i; Tarjan(i);

     }

     int ans=;

     for(int i=;i<=n;i++)

      if(gd[i]) ans++;

     printf("%d\n",ans);

     for(int i=;i<=n;i++)

      if(gd[i])

       printf("%d ",i);

     return ;

 }