76分求助 Orz
查看原帖
76分求助 Orz
877156
yyy_Logic楼主2023/8/20 22:05
//无向图:儿子→父亲的边不处理
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int n, m, ans;
vector<int>res;
struct node{
	int u, v, nex;
}e[N];
int head[N],cnt;

inline void add(int u, int v){
//	e[++cnt].u=u;
	e[++cnt].v=v;
	e[cnt].nex=head[u];
	head[u]=cnt;
}

int dfn[N], low[N], num;
inline void tarjin(int x, int root){
	dfn[x]=low[x]=++num;
	int child  = 0;
	for(int i = head[x]; i; i = e[i].nex){
		int v=e[i].v;
		if(!dfn[v]){//是x的儿子节点
			child++;
			tarjin(v,root);
			low[x]=min(low[x],low[v]);
			if(x!=root&&low[v]>=dfn[x]){
				ans++;
				res.push_back(x);
			}
		}
		low[x]=min(low[x], dfn[v]);
	}
	if(root==x&&child>=2){
		ans++;
		res.push_back(x);
	}
}

void solve()
{
	cin>>n>>m;
	for(int i = 1; i <= m; i++){
		int u, v; cin>>u>>v;
		add(u,v), add(v,u);
	}
	for(int i = 1; i <= n; i++){
		if(!dfn[i]){
//			root=i;
			tarjin(i,i);//设root:图不一定联通
		}
	}
	cout<<ans<<endl;
	sort(res.begin(),res.end());
	for(int i : res){
		cout<<i<<' ';
	}
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t = 1;
//	cin>>t;
	while(t--) solve();
	return 0;
}
2023/8/20 22:05
加载中...