20分求助
查看原帖
20分求助
418419
ko_no_lzx_da楼主2022/6/26 19:02
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
	int next;
	int u,v;
}edge[2000100];
int p=0;
int head[2000100];
int cnt,n,m,indexx,ans;
int c[10000000];
int root;
int dfn[2000100],low[2000100];
void add(int u,int v){
	edge[++cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
void dfs(int u,int fa){
	indexx++;
	dfn[u]=low[u]= indexx;
	int num=0;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(dfn[v]==0){
			dfs(v,u);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<=low[v]){
				num++;
				if(u!=root||num>1){
					ans++;
					c[++p]=u;
				}	
			}
		}else{
			low[u]=min(low[u],dfn[v]);
		}
	}
}
int main(){
	cin >>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin >>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++){
		if(dfn[i]==0){
			root=i;
			dfs(i,0);
		}
	}
	sort(c+1,c+p);
	cout <<ans<<endl;
	for(int i=1;i<=p;i++){
		cout <<c[i]<<endl;
	}
	return 0;
}
2022/6/26 19:02
加载中...