44分求调
查看原帖
44分求调
680006
xtzg楼主2023/5/7 12:16
#include<bits/stdc++.h>
#define debug(i) printf("%d\n",i)
using namespace std;
const int maxn=2e4+100;
vector<vector<int>>g;
int n,m,u,v,dep,rot,cnt;
int low[maxn],dfn[maxn],vis[maxn];

void tj(int u){
	dfn[u]=++dep,low[u]=dep;
	int tot;
	for(auto v:g[u]){
		if(!dfn[v]){
			tot++;
			tj(v);
			low[u]=min(low[v],low[u]);
			if((u==rot&&tot>1)||(u!=rot&&dfn[u]<=low[v]))vis[u]=1,cnt++;
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	g.resize(n+1);
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int u=1;u<=n;u++){
		if(!dfn[u]){
			rot=u;
			tj(u);
		}
	}
	cout<<cnt<<endl;
	for(int i=1;i<=n;i++){
		if(vis[i])cout<<i<<" ";
	}
}
2023/5/7 12:16
加载中...