【模板】割点

介绍

1. 何为割点： 在一个无向图中，如果去掉某一个点后这个图就不连通（x所在子图会被分成多份），那么这个点就被叫做割点。 如下图的点5和点1：

   

   如果去掉了这两个点这个图就不完整了。

2. 算法原理： 对于一张图，我们去dfs搜索他的时候都有一个时间戳（dfs序）但因为这个不是树嘛，所以对于每一个节点都有一个最小的一个可能的时间戳。同时记录最小时间戳比较子节点的最小时间戳和当前节点时间戳，就可以得到答案。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+12;
int cut[N],dfn[N],low[N],n,m,u,v,root,id,ans;
vector<int>edge[N];   //vector存边
void tarjan(int x)
{
  int son=0;
  dfn[x]=low[x]=++id;    //dfs序和最小时间戳的赋值
  for( int y:edge[x] )
  {
    if( !dfn[y] ) //当y节点并没有进行dfs的时候
    {
      tarjan(y);
      son++;
      low[x]=min( low[x] , low[y] );  //x节点的最小时间戳
      if( low[y]>=dfn[x] && x!=root )  //x并不是根节点并且x的子节点的最小时间戳不大于x的dfs序列，那么x就是割点
      {
        ans+=!cut[x];
        cut[x]=1;
      }
    }
    else low[x]=min( low[x],dfn[y] );  //反之y节点已经dfs了一遍，x节点的最小时间戳更新为从y到x的时间和当前的最小值
    if( x==root && son>1 )  //当x是根节点，并且儿子数大于1的时候，x节点就不能去掉（儿子数为1的时候，x去掉后并不能将图分成两份）
    {
      ans+=!cut[x];
      cut[x]=1;
    }
  }
}

int main(){
  scanf("%d%d",&n,&m);
  while(m--)
  {
    scanf("%d%d",&u,&v);
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  for(int i=1;i<=n;i++)
  {
    if( !dfn[i] )
    {
      root=i;
      tarjan(i);
    }
  }
  printf("%d\n",ans);
  for(int i=1;i<=n;i++)
  {
    if( cut[i] ) printf("%d ",i);
  
}