92 pts 求调
查看原帖
92 pts 求调
459188
zrt090604楼主2024/8/9 11:16
#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5;
int n, m, ans, cut[N], dfn[N], low[N], t, rt;  
vector<int> g[N];
void dfs(int u) {
	low[u] = dfn[u] = ++t;
	int chd = 0;
	for(auto v : g[u]) {
		if(!dfn[v]) {
			++chd;
			dfs(v);
			low[u] = min(low[u], low[v]);
			if(low[v]>=dfn[u] && u!=rt) cut[u] = true;
		}
		else low[u] = min(low[u], dfn[v]);
	}
	if(u==rt && chd>=2) cut[1] = true;
}
int main () {
	scanf("%d%d", &n, &m);
	for(int i = 1, u, v;i <= m;++i) {
		scanf("%d%d", &u, &v);
		g[u].push_back(v), g[v].push_back(u); 
	}
	for(int i = 1;i <= n;++i) 
		if(!dfn[i]) rt = i, dfs(i);
	for(int i = 1;i <= n;++i) ans += cut[i];
	printf("%d\n", ans);
	for(int i = 1;i <= n;++i)
		if(cut[i]) printf("%d ", i);
	return 0;
}
2024/8/9 11:16
加载中...