P3388 【模板】割点

AIsystem · 2019-07-08 20:16:17 · 个人记录

#include<bits/stdc++.h>
#define maxn 100001
using namespace std;
vector<int>g[maxn];
int dfn[maxn],gb[maxn],low[maxn];
int n,m;
void dfs(int u,int f)
{
    dfn[u]=++dfn[0];
    low[u]=dfn[u];
    int flag=0;
    for(int i=0;i<g[u].size();++i)
    {
        int v=g[u][i];
        if(v==f)
            continue;
        if(!dfn[v])
        {
            dfs(v,u),flag++;
        low[u]=min(low[u],low[v]);
        if(f!=0)
            if(low[v]>=dfn[u])
            gb[u]=1;
        }
        low[u]=min(low[u],dfn[v]);
        if(f==0)
            if(flag>=2)
            gb[u]=1;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
        dfs(i,0);
        int ans=0;
    for(int i=1;i<=n;++i)
        if(gb[i])
        ans++;
    printf("%d\n",ans);
    for(int i=1;i<=n;++i)
        if(gb[i])
        printf("%d ",i);
    return 0;
}