32分求调
查看原帖
32分求调
363145
Dino_Andy233楼主2022/9/24 14:10

RT, 改不出来了

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m;
struct Edge{
	int u,v,next;
}a[N];
int head[N],low[N],dfn[N],root,flag;
int tot=1,num;
int cnt;
bool cut[N];

void add(int u,int v)
{
	a[++tot].u=u;
	a[tot].v=v;
	a[tot].next=head[u];
	head[u]=tot;
}

void tarjan(int x,int in_edge)
{
	dfn[x]=low[x]=++num;
	flag=0;
	for(int i=head[x];i;i=a[i].next){
		int y=a[i].v;
		if(!dfn[y]){
			tarjan(y,i);
			low[x]=min(low[y],low[x]);
			if(low[y]>=dfn[x]){
				flag++;
				if(x!=root){
					cut[x]=1;
				}
				else if(flag>1) cut[x]=1;
			}
		}
		else if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);
	}
}

int main()
{
	
//	freopen("P3388_1.in","r",stdin);
//	freopen("P3388_1.txt","w",stdout);

	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(x==y) continue;
		add(x,y); add(y,x);
	}
	
	for(int i=1;i<=n;i++){
		if(!dfn[i]) root=i,tarjan(i,0);
	}
	
	for(int i=1;i<=n;i++){
		if(cut[i]) cnt++;
	}
	cout<<cnt<<endl;
	for(int i=1;i<=n;i++){
		if(cut[i]) cout<<i<<' ';
	}
	return 0;
}
2022/9/24 14:10
加载中...