#C240219B. 割点和桥

标签（Label）

• tarjan
• 模板

网址（Website）

$\qquad$ P3388 【模板】割点（割顶）

代码（Code）

#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#define N 20123
#define M 201234
using namespace std;
inline int input(){
	int x=0,f=1;char t=getchar();
	while(!isdigit(t)){if(t=='-')f=-1;t=getchar();}
	while(isdigit(t)){x=x*10+t-'0';t=getchar();}
	return x*f;
}

int n,m,ans;

int to[M],nxt[M],hd[N],tot;
void build(int x,int y){
	to[++tot]=y,nxt[tot]=hd[x],hd[x]=tot;
	to[++tot]=x,nxt[tot]=hd[y],hd[y]=tot;
}

int dfn[N],low[N],t;
bool cut[N],bri[M];
void tarjan(int x,int root){
	dfn[x]=low[x]=++t;
	int k=0;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];
		if(!dfn[y]){
			tarjan(y,root);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<low[y])	bri[e]=true;
			if(dfn[x]<=low[y] && x!=root) cut[x]=true;
			if(x==root) k++;
		}
		else low[x]=min(low[x],dfn[y]);
	}
	if(k>=2 && x==root) cut[x]=true;
}

//洛谷P3388
signed main(){
	n=input(),m=input();
	for(int i=1;i<=m;i++){
		int x=input(),y=input();
		build(x,y);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
	for(int i=1;i<=n;i++) if(cut[i]) ans++;
	printf("%d\n",ans);
	for(int i=1;i<=n;i++) if(cut[i]) printf("%d ",i);
	return 0;
}