76分求调
查看原帖
76分求调
441504
HedyLamarr520楼主2023/8/2 18:01
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int n,m; 
int num=0,ans=0;
vector<int>ver[27005];
void add(int x,int y){
	ver[x].push_back(y);
	ver[y].push_back(x);
}
int dfn[27005],low[27005];
bool cut[27005];
int root;
void tarjan(int x){
	dfn[x]=low[x]=++num;
	int flag=0;
	rep2(i,0,ver[x].size()){
		int y=ver[x][i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				flag++;
				if(x!=root||flag>1){
					cut[x]=1;
					ans++;
				}
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
int main(){
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	int a,b;
	rep(i,1,m){
		cin>>a>>b;
		if(a==b)continue;
		add(a,b);
	}
	rep(i,1,n){
		if(!dfn[i]){
			root=i;
			tarjan(i);
		}
	}
	cout<<ans<<endl;
	rep(i,1,n)if(cut[i])cout<<i<<" ";
	cout<<endl;
	return 0;
}
2023/8/2 18:01
加载中...