92pts求条
查看原帖
92pts求条
1034469
Meraktx楼主2024/12/17 21:06

rt WA on #11

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
const int maxn=1145140;
int n,m;
int low[maxn],dfn[maxn],f[maxn];
bool vis[maxn],inq[maxn];
vector<int> v[maxn];
int ans=0,child=0,sum=0;
priority_queue<int,vector<int>,greater<int> > q;
void tarjan(int st){
	child=0;
	dfn[st]=low[st]=++sum;
	//vis[st]=1;
	for(int i=0;i<(int)v[st].size();i++){
		if(!dfn[v[st][i]]){
			child++;
			f[v[st][i]]=st;
			tarjan(v[st][i]);
			low[st]=min(low[st],low[v[st][i]]);
			if((!f[st]) && child>=2){
				if(!inq[st]){
					ans++;
					q.push(st);
					inq[st]=1;
				}
			}else if((f[st]) && low[v[st][i]]>=dfn[st]){
				if(!inq[st]){
					ans++;
					q.push(st);
					inq[st]=1;
				}
			}
		}else if(v[st][i]!=f[st]){
			low[st]=min(low[st],dfn[v[st][i]]);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	cout<<ans<<endl;
	while(!q.empty()){
		cout<<q.top()<<' ';
		q.pop();
	}
	return 0;
}
2024/12/17 21:06
加载中...