08 简单并查集 ★★☆☆☆

并查集（Disjoint Set Union，DSU / Union-Find）用于维护若干互不相交的集合，支持「合并」与「查询」两种操作，是判断连通性、统计连通块、Kruskal 最小生成树、处理传递关系等问题的核心数据结构。

Tips：部分内容由 AI 生成，如发现问题请在评论区留言。

一、基本概念

并查集把每个集合组织成一棵有根树：根节点就是该集合的代表元，树中每个节点指向它的父亲。

• • 查询 find(x)：返回 x 所在集合的代表元（根）。
• • 合并 merge(x, y)：把 x、y 所在的两个集合合并成一个。

用数组 fa[] 存父指针：fa[i] 是节点 i 的父亲；根节点的父亲指向自己。初始时每个元素自成一个集合，即 fa[i] = i。

二、朴素实现

初始化

int fa[N];for (int i = 1; i <= n; i++) fa[i] = i;   // 每个点自成一个集合

查找 find（无优化）

沿父指针一直往上走，直到根：

int find(int x){    while (fa[x] != x) x = fa[x];   // 一路往上，直到根    return x;}

最坏情况树退化成一条链，单次 find 可达 。

合并 merge（无优化）

把 x 所在集合的根挂到 y 所在集合的根下：

void merge(int x, int y){    int fx = find(x), fy = find(y);    if (fx != fy) fa[fx] = fy;   // x 的根接到 y 的根下面}

三、路径压缩

问题：树可能退化成链，导致 find 很慢。

路径压缩：在 find 的过程中，把路径上的每个节点都直接指向根，这样以后再查就快了。

递归写法（最常用）：

int find(int x){    return fa[x] == x ? x : fa[x] = find(fa[x]);   // 递归，顺路把整条链压到根}

迭代写法（避免递归层数过深）：

int find(int x){    int r = x;    while (fa[r] != r) r = fa[r];   // 先找到根    while (fa[x] != x) {            // 再把路径上每个点直接挂到根        int t = fa[x];        fa[x] = r;        x = t;    }    return r;}

四、按秩合并与复杂度

另一种优化：合并时把规模小的集合挂到规模大的集合下面，避免树越接越高。

int fa[N], sz[N];   // sz[i] 是 i 所在集合的大小（只对根有意义）for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;int find(int x){    return fa[x] == x ? x : fa[x] = find(fa[x]);}void merge(int x, int y){    int fx = find(x), fy = find(y);    if (fx == fy) return;    if (sz[fx] < sz[fy]) swap(fx, fy);   // 让小集合挂到大集合下    fa[fy] = fx;    sz[fx] += sz[fy];}

复杂度：

• • 只做路径压缩：单次操作均摊 ，绝大多数题目已足够。
• • 路径压缩 + 按秩合并：单次操作均摊 ，其中  是阿克曼函数的反函数，增长极慢，实际可看作常数。

五、常见应用

1. 1. 判断连通 / 是否同集合：find(x) == find(y)。
2. 2. 统计连通块个数：初始 cnt = n，每次合并成功（fx != fy）时 cnt--。
3. 3. Kruskal 最小生成树：边按权排序，用并查集判断加入一条边是否会成环。
4. 4. 传递关系：朋友的朋友是朋友，用并查集合并传递闭包。
5. 5. 逆向思维：删点/删边难处理时，倒过来变成加点/加边（见例题 4）。

六、例题

1. P3367 【模板】并查集

题意：n 个元素，支持两种操作——合并 a、b；查询 a、b 是否在同一集合。

#include <bits/stdc++.h>using namespace std;const int N = 10005;int fa[N];int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }int main(){    int n, m; cin >> n >> m;    for (int i = 1; i <= n; i++) fa[i] = i;    while (m--) {        int op, x, y; cin >> op >> x >> y;        if (op == 1) fa[find(x)] = find(y);            // 合并        else cout << (find(x) == find(y) ? "Y\n" : "N\n");    }    return 0;}

2. P3958 奶酪

题意：一块高度为 h 的奶酪内有 n 个球形空洞（半径均为 r，给出球心坐标）。问能否从下表面走到上表面——两个球相交或相切即可通过，球与表面相切即可到达表面。

思路：把每个空洞当作节点，相交/相切的球合并；再设两个虚拟节点 0（下表面）、n+1（上表面），球心 z ≤ r 则接下表面，z ≥ h − r 则接上表面。最后看 find(0) == find(n+1)。

#include <bits/stdc++.h>using namespace std;const int N = 1005;typedef long long ll;int fa[N];ll x[N], y[N], z[N];int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }void merge(int a, int b){ fa[find(a)] = find(b); }int main(){    int T; cin >> T;    while (T--) {        int n; ll h, r;        cin >> n >> h >> r;        for (int i = 0; i <= n + 1; i++) fa[i] = i;   // 0 下表面, n+1 上表面        for (int i = 1; i <= n; i++) {            cin >> x[i] >> y[i] >> z[i];            if (z[i] <= r) merge(i, 0);            if (z[i] >= h - r) merge(i, n + 1);        }        for (int i = 1; i <= n; i++)            for (int j = i + 1; j <= n; j++) {                long double dx = (long double)x[i] - x[j];                long double dy = (long double)y[i] - y[j];                long double dz = (long double)z[i] - z[j];                if (dx*dx + dy*dy + dz*dz <= (long double)4*r*r) merge(i, j);            }        cout << (find(0) == find(n + 1) ? "Yes\n" : "No\n");    }    return 0;}

3. P1955 [NOI2015] 程序自动分析

题意：给定 n 个约束，每个形如 i = j（相等）或 i ≠ j（不等），问能否找到一组取值使所有约束同时成立。

思路：先处理所有「相等」约束并合并；再检查所有「不等」约束，若两个变量已在同一集合则矛盾。因为 i、j 可达 ，需要先离散化。

#include <bits/stdc++.h>using namespace std;const int N = 2000005;int fa[N];int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }int main(){    ios::sync_with_stdio(false); cin.tie(nullptr);    int T; cin >> T;    while (T--) {        int n; cin >> n;        vector<array<int,3>> c(n);        vector<int> a;        a.reserve(2 * n);        for (auto &t : c) {            cin >> t[0] >> t[1] >> t[2];            a.push_back(t[0]);            a.push_back(t[1]);        }        sort(a.begin(), a.end());        a.erase(unique(a.begin(), a.end()), a.end());        int m = a.size();        for (int i = 0; i < m; i++) fa[i] = i;        auto id = [&](int v) { return lower_bound(a.begin(), a.end(), v) - a.begin(); };        // 先合并所有"相等"约束        for (auto &t : c) if (t[2] == 1)            fa[find(id(t[0]))] = find(id(t[1]));        // 再检查"不等"约束        bool ok = true;        for (auto &t : c) if (t[2] == 0)            if (find(id(t[0])) == find(id(t[1]))) { ok = false; break; }        cout << (ok ? "YES\n" : "NO\n");    }    return 0;}

4. P1197 [JSOI2008] 星球大战

题意：n 个星球、m 条双向通道，有 k 次攻击，每次摧毁一个星球。求初始连通块数，以及每次攻击后的连通块数。

思路：摧毁点不好处理，反过来——先删掉所有被摧毁的点求连通块数，再倒序「恢复」被摧毁的点，每恢复一个就把它与已恢复的邻点合并。

#include <bits/stdc++.h>using namespace std;const int N = 400005;vector<int> g[N];int fa[N], des[N], vis[N], ans[N];int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }int main(){    ios::sync_with_stdio(false); cin.tie(nullptr);    int n, m; cin >> n >> m;    for (int i = 0; i < m; i++) {        int u, v; cin >> u >> v;        g[u].push_back(v);        g[v].push_back(u);    }    int k; cin >> k;    for (int i = 1; i <= k; i++) { cin >> des[i]; vis[des[i]] = 1; }    for (int i = 0; i < n; i++) fa[i] = i;    int cnt = n - k;   // 仅存活的点，先各自孤立    for (int u = 0; u < n; u++) if (!vis[u])        for (int v : g[u]) if (!vis[v]) {            int fu = find(u), fv = find(v);            if (fu != fv) { fa[fu] = fv; cnt--; }        }    ans[k + 1] = cnt;    for (int i = k; i >= 1; i--) {        int u = des[i];        vis[u] = 0;   // 恢复        cnt++;        for (int v : g[u]) if (!vis[v]) {            int fu = find(u), fv = find(v);            if (fu != fv) { fa[fu] = fv; cnt--; }        }        ans[i] = cnt;    }    for (int i = 1; i <= k + 1; i++) cout << ans[i] << '\n';    return 0;}

七、总结

• • 并查集用数组 fa[] 维护一棵树的父指针，根的代表元是自己。
• • find 加路径压缩，merge 可选按秩合并，两者结合复杂度近似常数。
• • 应用：判断连通性、统计连通块、Kruskal、传递关系、逆向加点/加边。