图论--割点--Tarjan

#include<iostream>

#include<stdio.h>

#include<vector>

using namespace std;

const int maxn=100010;

int head[maxn],ver[maxn*2],Next[maxn*2];

int dfn[maxn],low[maxn],sta[maxn];

int n,m,tot,num,root;

bool cut[maxn];

void add(int x,int y)

{

    ver[++tot]=y;

    Next[tot]=head[x];

    head[x]=tot;

}

void tarjan(int x)

{

    dfn[x]=low[x]=++num;

    int flag=0;

    for(int i=head[x];i;i=Next[i])

    {

        int y=ver[i];

        if(!dfn[y])

        {

            tarjan(y);

            low[x]=min(low[x],low[y]);

            if(low[y]>=dfn[x])

            {

                flag++;

                if(x!=root||flag>1) cut[x]=1;

            }

        }

        else low[x]=min(low[x],dfn[y]);

    }

}

int main()

{

    cin>>n>>m;

    tot=1;

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

    {

        int x,y;

        scanf("%d %d",&x,&y);

        if(x==y) continue;

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

    }

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

    {

        if(!dfn[i]) root=i,tarjan(i);

    }

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

        if(cut[i]) printf("%d ",i);

}
巴特西

图论--割点--Tarjan

最新文章

热门文章
