全RE+WA求调
查看原帖
全RE+WA求调
592897
GrainRain25楼主2024/6/13 17:25
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e4+5,maxm=1e5+5;
template <typename T> void read(T &x){
	x=0;int f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) f=-1;
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
int head[maxn],ver[maxm*2],Next[maxm*2],tot,num,root,ans;
int n,m;
int dfn[maxn],low[maxn],IS[maxn];

void add(int x,int y){
	ver[++tot]=y;Next[tot]=head[x];head[x]=tot;
}

void tarjan(int x,int fa){
	dfn[x]=low[x]=++num;
	int flag=0;
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(!dfn[y]){
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				flag++;
				IS[x]=1,ans++;
			}
		}
		else if(y!=fa)low[x]=min(low[x],dfn[y]);
	}
	if(x==root&&flag==1) IS[x]=0,ans--;
}

int main(){
	read(n);read(m);
	while(m--){
		int x,y;
		read(x);read(y);if(x==y)continue;
		add(x,y);add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) root=i,tarjan(i,i);
	}
	printf("%d\n",ans);
	for(int i=1;i<=n;i++){
		if(IS[i])printf("%d ",i);
	}
	return 0;
}
2024/6/13 17:25
加载中...