求助
查看原帖
求助
400333
qzilr楼主2022/7/10 15:22
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct edge{
	int u,v,nxt;
}e[maxn<<1];
int h[maxn],tot=0;
void add(int u,int v){
	e[++tot]=(edge){u,v,h[u]};
	h[u]=tot;
}
int dfn[maxn],low[maxn],par[maxn],id=0,vis[maxn],ans[maxn],cnt=0,ch;
void Tarjan(int pos){
	vis[pos]=1,ch=0;
	dfn[pos]=low[pos]=++id;
	for(int i=h[pos];i;i=e[i].nxt){
		int v=e[i].v;
		if(!vis[v]){
			ch++;
			par[v]=pos;
			Tarjan(v);
			low[pos]=min(low[pos],low[v]);
			if(par[pos]!=pos&&low[v]>=dfn[pos])	ans[pos]=1;
		}
		else
			low[pos]=min(low[pos],dfn[v]);
	}
	if(par[pos]==pos&&ch>=2)	ans[pos]=1;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++)	cin>>u>>v,add(u,v),add(v,u);
	for(int i=1;i<=n;i++)
		if(!vis[i])	par[i]=i,Tarjan(i);
	for(int i=1;i<=n;i++)
		if(ans[i])	cnt++;
	cout<<cnt<<endl;
	for(int i=1;i<=n;i++)
		if(ans[i])	cout<<i<<" ";
	return 0;
}
2022/7/10 15:22
加载中...