84分求调
查看原帖
84分求调
762271
Eric__yang楼主2023/10/8 21:19
#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
#define ll long long
#define pr printf
using namespace std;
const int N=1e5+5;
vector <int> a[N];
int dfn[N],low[N],tot=0,root,child=0;
bool cut[N];
int an[N];
template <typename T>
void in(T &x){
	char c=getchar();
	int f=1;
	while ((c>'9' || c<'0') && c!='-') c=getchar();
	if(c=='-') f=-1, c=getchar();
	for(x=0; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
	x*=f;
}
void tarjan(int w){
	dfn[w]=low[w]=++tot;
	for(int i=0; i<a[w].size(); i++){
		if(!dfn[a[w][i]]){
			tarjan(a[w][i]);
			low[w]=min(low[w],low[a[w][i]]);
			if(low[a[w][i]]>=dfn[w]){
				child++;
				if(w!=root||child>=2){
					cut[w]=1;
				}
			}
		}
		else low[w]=min(low[w],dfn[a[w][i]]);
	}
}
int main(){
//	freopen("p3388_6.in","r",stdin);
//	freopen("123.out","w",stdout);
	int n,m,s,d;
	in(n),in(m);
	rep(i,1,m){
		in(s),in(d);
		a[s].push_back(d);
		a[d].push_back(s);
	}
	root=1;
	rep(i,1,n){
		if(!dfn[i]) tarjan(i);
	}
	int ans=0;
	rep(i,1,n){
		if(cut[i]) ans++,an[ans]=i;
	}
	cout<<ans-1<<endl;
	rep(i,2,ans) cout<<an[i]<<" ";
	return 0;
}

2023/10/8 21:19
加载中...