割点和割边

佚名 6年前 (2019-04-10) 随笔 935人围观抢沙发百度已收录

关于割点的详细讲解见这篇文章

//时间复杂度：O(N+M) 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=20010;
int N, M, bj[maxn], ans=0, dfn[maxn], low[maxn], fa[maxn], timestamp=0; 
struct edge{ int t; edge *nxt; edge(int to, edge *next){t=to, nxt=next; } };
edge *h[maxn];
void add(int u, int v){ h[u]=new edge(v, h[u]); h[v]=new edge(u, h[v]); }   //add一次加两条边，无向图 

void tarjan(int x)
{ 
    dfn[x]=low[x]=++timestamp;
    int child=0;                                                            //child为结点的子树数量 
    for(edge *p=h[x]; p; p=p->nxt)
    {
        if(p->t==fa[x]) continue;                                           //不能往父亲方向走 
        if(dfn[p->t])   low[x]=min(low[x], low[p->t]);                      //发现返祖边，更新low值 
        else
        {
            fa[p->t]=x; 
            tarjan(p->t);
            low[x]=min(low[x], low[p->t]);
            if(fa[x]!=0 && low[p->t]>=dfn[x]) bj[x]=1;                      //x不是根结点，且其孩子的low值>=其dfn值，x为割点 
            if(fa[x]==0)    child++;                                        //如果x是根结点，在此情况下发现其一颗子树 
            if(low[p->t]>=dfn[x])    记录这条边(x, p->t);                   //判断割边（桥）就这么简单，自己意会吧……
        }
    }
    if(fa[x]==0 && child>=2)    bj[x]=1;                                    //如果x是根结点且子树>=2，x为割点 
}

int main()
{
    scanf("%d%d", &N, &M);
    for(int i=1, x, y; i<=M; i++)       scanf("%d%d", &x, &y), add(x, y);
    for(int i=1; i<=N; i++)                                                 //考虑原图可能是非连通的 
        if(!dfn[i]) tarjan(i);
    for(int i=1; i<=N; i++) if(bj[i])   ans++;                              //统计割点个数 
    printf("%d\n", ans);
    for(int i=1; i<=N; i++) if(bj[i])   printf("%d ", i);                   //由小到大输出割点 
    return 0;
}