84pts蒟蒻求助
查看原帖
84pts蒟蒻求助
936204
Ace2012楼主2024/5/25 21:22

rt.

code:

#include <bits/stdc++.h>
using namespace std;
#define mxx 20240525
int n,m;
int root;
int num;
int ch;
int head[100010];
int cnt;
int a[100010];
int q=1;
int maxx;

struct edge{
	int to,nxt;
}e[1000010];
void add(int u,int v){
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt++;
}
bool ins[100010];
int dfn[100010],low[100010];
void tarjan(int u){
	dfn[u]=low[u]=++num;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				if(u==root)ch++;
				else a[u]++;
			}
		}
		else{
			low[u]=min(low[u],dfn[v]);
		}
	}
}
int main(){
	cin>>n>>m;
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
		    root=i;
			tarjan(i);
			if(ch>1)a[i]=1;
		}
	}
	maxx=0;

    for(int i=1;i<=n;i++){
        if(a[i])maxx++;
    }
	cout<<maxx<<endl;
	for(int i=1;i<=n;i++){
		if(a[i])cout<<i<<" ";
    }
    
    
	return 0;
}

84pts84 pts

2024/5/25 21:22
加载中...