求调 92pts
查看原帖
求调 92pts
1046508
Sparse_Table楼主2024/12/2 17:07
#include <bits/stdc++.h>
using namespace std;

int n, m;
int dfn[20005], tot, low[20005];
vector<int> g[20005];
bitset<20005> cut;

void dfs(int u, int st) {
	dfn[u] = low[u] = ++tot;
	int child = 0;
	for (auto v : g[u])
		if (!dfn[v]) {
			dfs(v, st);
			low[u] = min(low[v], low[u]);
			child++;
			if (low[v] >= dfn[u] && u != st)
				cut[u] = 1;
		} else
			low[u] = min(dfn[v], low[u]);
	if (child > 1 && u == st)
		cut[1] = 1;
}

int main() {
	cut.reset();
	cin >> n >> m;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			dfs(i, i);
	cout << cut.count() << '\n';
	for (int i = 1; i <= n; i++)
		if (cut[i])
			cout << i << ' ';
	return 0;
}
2024/12/2 17:07
加载中...