12分求助
查看原帖
12分求助
446796
120MB楼主2021/7/4 15:58
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
/*
6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6


*/
const int MAXE = 1000100, MAXD = 10100;
int idx=0,head[MAXD],n,m,dfn[MAXE]={0},ic[MAXE]={0},dfstime = 0;int ans = 0;
struct verticese{
	int v,next;
}edge[MAXD];

void add(int u,int v){
	edge[idx].v = v;
	edge[idx].next = head[u];
	head[u] = idx;
	++idx;
}

int dfs(int u,int parent){
	int lowu = dfn[u] = ++dfstime, lowv, children = 0;
	for(int i = head[u]; i != -1; i = edge[i].next){
		int v = edge[i].v;
		if(dfn[v] == 0){
			if(parent < 0){
				children++;
			}
			lowv = dfs(v, u);
			lowu = min(lowu,lowv);
			if(lowv >= dfn[u]&&parent > 0)
				ic[u] = 1;
			
		}
		lowu = min(lowu, dfn[v]);
	}
	if(parent < 0 && children >= 2)
		ic[u] = 1;
	return dfn[u] = lowu;
}


int main(){
	memset(head,-1,sizeof(head));
	cin>>n>>m;
	for(int u , v , i = 1; i <= m; i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
		if(i == m) {
			//cout<<endl; for(int i = 1; i <= n; i++){for(int j = head[i]; j != -1; j = edge[j].next){cout<<i<<" "<<edge[j].v<<endl;}}
		}
	}
	for(int i = 1; i<=n;i++){
		if(dfn[i]==0){
			dfstime = 0;
			dfs(i,-1);
		}
	}
	
	for(int i = 1; i<=n; i++){
		if(ic[i]) ans++;
	}
	cout<<ans<<endl;
	for(int i = 1; i<= n; i++){
		if(ic[i]) cout<<i<<endl;
	}
	
	return 0;
}
2021/7/4 15:58
加载中...