无向图的割点
作者:
夜深人未静
,
2022-08-24 16:54:15
,
所有人可见
,
阅读 136
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10,M=2e5+10;
struct node{
int to,nex;
}e[M];
int n,m,idx,cnt,root;
int dfn[N],low[N];
int h[M];
int st[N];
void add(int a,int b)
{
idx++;
e[idx]={b,h[a]};
h[a]=idx;
}
void tarjan(int u)
{
dfn[u]=low[u]=++cnt;
int flag=0;
for(int i=h[u];i;i=e[i].nex)
{
int j=e[i].to;
if(!dfn[j]){
tarjan(j);
low[u]=min(low[u],low[j]);
if(dfn[u]<=low[j]){
flag++;
if(u!=root || flag>1) st[u]=true;
}
}
else low[u]=min(low[u],dfn[j]);
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
int ans=0;
for(int i=1;i<=n;i++) if(!dfn[i]) root=i,tarjan(i);
for(int i=1;i<=n;i++) if(st[i]) ans++;
cout<<ans<<endl;
for(int i=1;i<=n;i++) if(st[i]) cout<<i<<" ";
cout<<endl;
return 0;
}