Definition&Solution

　　在一个无向联通图中，如果删除一个点，该图变得不连通，那么该点称作该图的割点。注意，割点可能不止一个。

　　对于无向不连通图，一个点是割点当且仅当它是它所在的联通分量的割点。

　　特别的，如果一个连通分量只包含一个点X，那么点X为一个割点。

　　对于一个图，求他的割点，只需要对每个连通分量进行dfs，在dfs树上，一个非根节点是割点当且仅当他的子树的反向边全部指向他的子树。如果使用low[i]来代表点i所能连接的最小dfs序的点，dfn代表该点的dfs序，一个非根节点i是割点当且仅当对于所有的to=edge[j].to，满足low[to]>=dfn[i]。在dfs过程中，易于顺手求出dfs序和low值。

　　对于一个根节点，根节点是割点当且仅当它有两个及以上子树。

Example

Description

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

Input

第一行输入n,m

下面m行每行输入x,y表示x到y有一条边

Output

第一行输出割点个数

第二行按照节点编号从小到大输出节点，用空格隔开

Sample Input

6 71 21 31 42 53 54 55 6

Sample Output

1 5

Solution

板子题。

Code

#include
     
      #define maxn 100010#define maxm 200010inline void qr(int &x) {    char ch=getchar(),lst=NULL;    while(ch>'9'||ch<'0') lst=ch,ch=getchar();    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();    if(lst=='-') x=-x;}template 
      
       inline T mmax(const T &a,const T &b) {
   if(a>b) return a;return b;}template 
       
        inline T mmin(const T &a,const T &b) {
   if(a
        
         inline T mabs(const T &a) {
   if(a>=0) return a;return -a;}template 
         
          inline void spaw(T &a,T &b) {T temp=a;a=b;b=temp;}int n,m,a,b;int ans[maxn],cnt;bool is_cut[maxn];struct Edge {    int to,nxt;};Edge edge[maxm];int hd[maxn],ecnt;inline void cont(int from,int to) {    edge[++ecnt].to=to;    edge[ecnt].nxt=hd[from];    hd[from]=ecnt;}int dfn[maxn],low[maxn],vistime;void tarjan(int,int);int main() {    qr(n);qr(m);    while(m--) {        a=b=0;qr(a);qr(b);        cont(a,b); cont(b,a);    }    for(int i=1;i<=n;++i) {        if(!dfn[i]) tarjan(i,i);        if(is_cut[i]) ans[++cnt]=i;    }    printf("%d\n",cnt);    for(int i=1;i<=cnt;++i) printf("%d ",ans[i]);}void tarjan(const int u,const int rt) {    int v,cld=0;    dfn[u]=low[u]=++vistime;    for(int i=hd[u];i;i=edge[i].nxt) {        v=edge[i].to;        if(!dfn[v]) {            tarjan(v,rt);            low[u]=mmin(low[u],low[v]);            if(u==rt) ++cld;            else if(low[v]>=dfn[u]) is_cut[u]=true;        }        low[u]=mmin(low[u],dfn[v]);    }    if((rt==u)&&(cld>1)) is_cut[u]=true;}
         
        
       
      
     

Summary

tarjan算法有很多，不要混淆（tarjan爷牛逼

区分代码中v和u，否则会死。

区分代码中dfn和low。否则会死