自动搬运

查看原文

来自洛谷，原作者为

	WorldMachine 请引领我至夜晚熠熠闪烁的群星之下

搬运于2025-08-24 23:06:41，当前版本为作者最后更新于2024-12-09 22:33:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

小水题，之前想过这样的东西，碰巧看到了这道题就做一下吧。

这个题 tarjan 肯定是做不了的，因为 $\mathcal O(m)$ 的空间开不下。

割边一定在生成树上，那我们弄出原图的一棵生成树，现在就是要求有哪些树边没有被覆盖。对每条非树边 $(u,v)$，我们随机一个权值 $w$，将 $a_u$ 加上 $w$，$a_v$ 减去 $w$。这样 $(u,v)$ 这条边的影响刚好会在 $\text{lca}(u,v)$ 处被消去，随机权值下如果 $v$ 子树内的 $a_i$ 之和为 $0$，那么 $(\text{fa}_v,v)$ 有很大概率是一条割边。

时间复杂度 $\mathcal O(n\alpha(n)+m)$，瓶颈在于并查集，所以通常情况下没啥优势。

代码已省去快读。

#include <bits/stdc++.h>
using namespace std;
// namespace IO
#define cin io
#define cout io
typedef long long ll;
const int N = 100005, M = 6e6 + 5;
int n, m, fa[N], siz[N];
ll a[N];
vector<int> G[N];
mt19937 rnd(time(0));
int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]); }
void dfs(int u, int f) {
	for (int v : G[u]) {
		if (v == f) continue;
		dfs(v, u), a[u] += a[v];
		if (!a[v]) cout << u << ' ' << v << '\n';
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
	int u, v, fu, fv;
	ll w;
	while (m--) {
		cin >> u >> v;
		fu = get(u), fv = get(v);
		if (fu != fv) {
			if (siz[fu] > siz[fv]) swap(fu, fv);
			fa[fu] = fv, siz[fv] += siz[fu];
			G[u].emplace_back(v), G[v].emplace_back(u);
		} else w = rnd(), a[u] += w, a[v] -= w;
	}
	for (int i = 1; i <= n; i++) if (i == fa[i]) dfs(i, 0);
}