92分 求条ToT
查看原帖
92分 求条ToT
1642090
gyq456楼主2025/2/7 21:19
#include<bits/stdc++.h> 
using namespace std;
int n,m,inde,root,num[200002],low[200002],u[200002],v[200002],first[200002],next1[200002],ans;
bool flag[20001],book[20001];
void dfs(int cur,int father){
	int child,i,k;
	inde++;
	num[cur]=inde;
	low[cur]=inde;
	k=first[cur];
	book[cur]=1;
	for(;k!=-1;k=next1[k]){
		if(num[v[k]]==0){
			child++;
			dfs(v[k],cur);
			low[cur]=min(low[cur],low[v[k]]);
			if(cur!=root&&low[v[k]]>=num[cur])
				flag[cur]=1;
			if(cur==root&&child==2)
				flag[cur]=1;
		}
		else if(v[k]!=father){
			low[cur]=min(low[cur],num[v[k]]);
		}
	}
	return;
}
int main(){
	cin>>n>>m;
	int x,y;
	memset(first,-1,sizeof first);
	memset(next1,-1,sizeof next1);
	for(int i=1;i<=m*2;i+=2){
		cin>>u[i]>>v[i];
		next1[i]=first[u[i]];
		first[u[i]]=i;
		u[i+1]=v[i];
		v[i+1]=u[i];
		next1[i+1]=first[u[i+1]];
		first[u[i+1]]=i+1;
	}
	for(int i=1;i<=n;i++){
		if(book[i]==0){
			root=i;
			dfs(i,root);
			inde=0;
			memset(num,0,sizeof num);
			memset(low,0,sizeof low);
		}
	}
	for(int i=1;i<=n;i++){
		if(flag[i])
			ans++;
	}
	cout<<ans<<endl;
	for(int i=1;i<=n;i++){
		if(flag[i])
			cout<<i<<" ";
	}
	return 0;
}
2025/2/7 21:19
加载中...