WA on 11,92pts
查看原帖
WA on 11,92pts
799098
chengzihan620楼主2024/3/12 19:53
#include<bits/stdc++.h>
using namespace std;
const int maxn=20*1e5;
int dfn[maxn],low[maxn],ans[maxn];
int n,m,num,idx,root,child,sum;
vector<int>g[maxn];
void tarjan(int x){
	child=0;
	int y;
	dfn[x]=low[x]=++idx;
	for(int i=0;i<g[x].size();i++){
		y=g[x][i];
		if(!dfn[y]){
			if(x==root)child++;
			tarjan(y);low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]&&x!=root)ans[x]++;
		}
		else
			low[x]=min(low[x],dfn[y]);
	}
	if(x==root&&child>=2)ans[x]++;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])root=i,tarjan(i);
	for(int i=1;i<=n;i++)
		if(ans[i])sum++;
	cout<<sum<<endl;
	for(int i=1;i<=n;i++)
		if(ans[i])cout<<i<<' ';
	return 0;
}
2024/3/12 19:53
加载中...