题解：P11360 [CEOI 2015] 管道

· · 题解

题目传送门

思路借鉴 第一篇 题解

题目大意

求割边。空间限制：16MB。

1 \le n \le 10 ^ 5$，$1 \le m \le 6 \times 10 ^ 6

题目分析

由于卡空间，所以我们不能用 Tarjan。

注意到：割边一定在原图的 每一个生成树 上面。

拿样例举例。(1, 8) 这条边一定在左边这个连通块的每一个生成树上。

如果把 (1, 8) 和 (9, 10) 这两条割边删掉，我们会发现整个图变成两块，\{1, 6, 7\} 和 \{2, 3, 4, 5, 8\}。先叫它们为 “割块”。

我们给每个点设一个权值 a。

我们发现对于一条非树边 (u, v)，如果让 a_u 加上一个随机权值 w，a_v 减去 w，那么在 lca(u, v) 处这条边就不会再造成影响了。而如果 v 的子树上的所有非树边都不造成影响了即 a_v = 0 时，意味着 v 的子树就是一个“割块”，所以 (fa_v, v) 就是一条割边。

code

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
    ll res = 0, f = 1; char ch = gc();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
    while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
    return res * f;
}
inline void write(ll x)
{
    if (x < 0) x = -x, pc('-');
    if (x > 9) write(x / 10);
    pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 1e5 + 5;
mt19937 Rand(time(0)); // 随机 
vector<int> e[N]; // 存生成树
int fa[N], siz[N]; // 并查集 
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int a[N]; // 权值 
void dfs(int u, int fa)
{
    for (int v : e[u])
    {
        if (v == fa) continue;
        dfs(v, u), a[u] += a[v];
        if (a[v] == 0) writech(u, ' '), writech(v, '\n'); // "割块"
    }
}
int main()
{
    int n = read(), m = read();
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int u = read(), v = read();
        int s = find(u), t = find(v);
        if (s != t) // 加入生成树 
        {
            if (siz[s] > siz[t]) swap(s, t);
            fa[s] = t, siz[t] += siz[s];
            e[u].pb(v); e[v].pb(u);
        }
        else 
        {
            int w = Rand(); // 随机 
            a[u] += w, a[v] -= w;
        }
    }
    for (int i = 1; i <= n; i++) if (fa[i] == i) dfs(i, 0); // 一个连通块 
    return 0;
}