萌新不是妹子刚学oi,44pts求调
查看原帖
萌新不是妹子刚学oi,44pts求调
448018
KAqwq楼主2024/8/14 13:33
#include <bits/stdc++.h>
#define N 100005
#define pll std::pair<LL, LL>
#define mp std::make_pair
#define ft first
#define sd second

typedef long long LL;

LL n, m;
LL head[N << 2], tail[N << 2], nxt[N << 2], tot = 1;

inline void add_edge(LL u, LL v) {
	tail[++tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

pll edge[N];
std::stack<LL> s;
std::vector<LL> bel[N];

LL dfn[N], low[N], deg[N];
LL cnt, idx, res;

inline void dfs(LL x, LL fa) {
	low[x] = dfn[x] = ++cnt;
	s.push(x);
	for (LL i = head[x]; i; i = nxt[i]) {
		if (i != (fa ^ 1)) {
			LL ed = tail[i];
			if (!dfn[ed]) {
				dfs(ed, i);
				low[x] = std::min(low[x], low[ed]);
				if (low[ed] >= dfn[x]) {
					bel[++idx].push_back(x);
					++deg[x];
					LL v = s.top(); s.pop();
					while (v != ed) {
						v = s.top(); s.pop();
						bel[idx].push_back(v);
						++deg[v];
					}
				}
			} else low[x] = std::min(low[x], dfn[ed]);
		} 
	}
}

int main() {
	std::cin >> n >> m;
	while (m--) {
		LL u, v;
		std::cin >> u >> v;
		add_edge(u, v); add_edge(v, u);
	}
	for (LL i = 1; i <= n; ++i) if (!dfn[i]) {dfs(i, -1); while(!s.empty()) s.pop();}
	LL ans = 0;
	for (LL i = 1; i <= n; ++i) {if (deg[i] > 1) ++ans;}
	std::cout << ans << '\n'; 
	for (LL i = 1; i <= n; ++i) {
		LL fa = 0;
		if (deg[i] > 1) {
			if (fa) std::cout << ' ';
			fa = 1;
			std::cout << i;
		}
	}
	return 0;
}
2024/8/14 13:33
加载中...