44 分求助
查看原帖
44 分求助
515129
TLEWA楼主2022/10/22 21:55

rt:

#include<iostream>
using namespace std;

int first[200050],p;
struct Node{
	int next,to;
}arr[1000050];

void add(int u,int v) {
	arr[++p].next=first[u];
	first[u]=p;
	arr[p].to=v;
}

int n,m,u,v;
int dfn[200050],low[200050],dfncnt;
bool vis[200050],ge[200050];
int summge;

void tarjan(int u,int fa) {
	int maxn=0,child=0;
	vis[u]=1;
	low[u]=dfn[u]=++dfncnt;
	for(int i=first[u];i;i=arr[i].next){
		if(!vis[arr[i].to]) {
			tarjan(arr[i].to,fa);
			low[u]=min(low[u],low[arr[i].to]);
			if(u==fa) ++child;
			if(low[arr[i].to]>=dfn[u]&&u!=fa) ge[u]=1;
		}else low[u]=min(low[u],dfn[arr[i].to]);
	}
	if(child>2&&u==fa) ge[u]=1;
	summge+=ge[u];
}

int main() {
	cin >> n >> m;
	for(int i=1;i<=m;++i) {
		cin >> u >> v;
		add(u,v);
		add(v,u);
	}
	
	for(int i=1;i<=n;++i)
		if(dfn[i]==0)
			tarjan(i,i);
	cout << summge << endl;
	for(int i=1;i<=n;++i) {
		if(ge[i]) cout << i << endl;
	}
	
	return 0;
}
2022/10/22 21:55
加载中...