并查集 | blog of peter

问题引入

$n$ 个元素，不断接收「 $x$ 与 $y$ 同集合」的合并指令，并查询「 $x$ 与 $y$ 是否同集合」「当前多少个独立集合」。图遍历每次查询 $O(n)$ ， $10^5$ 量级即超时。关键在于：只关心集合归属，不关心内部连接结构–并查集（Union-Find / DSU[Disjoint Set Union]） 即为此设计，配合两种优化后单次操作均摊近似 $O(1)$ 。

核心思想：用森林表示集合

每个集合是一棵树，根为代表元。每个节点保存 parent 指针，根的 parent 指向自身。

集合 {1,2,3,5,8}：        集合 {4,6,7}：

        1                       4
       / \                     / \
      2   3                   6   7
     / \
    5   8

三个核心操作：

makeSet(x)：parent[x] = x。
find(x)：沿 parent 走到根。
union(x, y)：find 出两根，不同则把一棵根挂到另一棵下。

合并只需修改一个指针，查询沿父链走到根。但树形不加控制可退化为链，单次 find 最坏 $O(n)$ 。

基本实现与两大优化

未优化实现：

struct UnionFind {
    vector<int> parent;                 // parent[x]：x 的父节点，根的父节点是自身
    explicit UnionFind(int n) : parent(n) {
        iota(parent.begin(), parent.end(), 0);  // 初始每个元素自成一个集合
    }

    int find(int x) {                   // 查找 x 所在集合的代表元（根）
        while (parent[x] != x)
            x = parent[x];              // 沿父链一路向上直到根
        return x;
    }

    void unite(int x, int y) {          // 合并 x、y 所在的集合
        int rx = find(x), ry = find(y);
        if (rx == ry) return;           // 已同集合，无需合并
        parent[rx] = ry;                // 把 rx 整棵树挂到 ry 下
    }

    bool connected(int x, int y) {      // 查询 x、y 是否同集合
        return find(x) == find(y);
    }
};

依次 unite(1,2), unite(2,3), ..., unite(n-1,n) 可退化为长度 $n$ 的链。两种优化单独使用均达 $O(\log n)$ ，组合达 $O(\alpha(n))$ 。

路径压缩（Path Compression）

find 时将路径上所有节点直接挂到根下：

find(8) 前：          find(8) 后：
        1                     1
       / \                   /|\
      2   3                 2 3 8
     / \                    |
    5   8                   5

递归实现（一行）：

1
2
3

int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);  // 递归到根，沿途节点直接挂到根下
}

两趟迭代实现（避免深递归）：

int find(int x) {
    int r = x;
    while (parent[r] != r) r = parent[r];       // 第一趟：沿父链找根
    while (parent[x] != r) {
        int nxt = parent[x];                    // 先保存原父节点
        parent[x] = r;                          // 当前节点直接挂到根下
        x = nxt;                                // 继续处理原父节点
    } // 第二趟：压缩路径

    return r;
}

变体路径减半：沿父链上行时改指祖父，单趟完成，与按秩组合同样 $O(\alpha(n))$ ：

int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];  // 改指祖父节点，每隔一层跳一级
        x = parent[x];
    }
    return x;
}

按秩合并 / 按大小合并

始终将较小（矮）的树挂到较大（高）的树下，抑制树高增长。

按大小合并（size 本身即常用信息，更实用）：

vector<int> parent, sz;                 // sz[x]：以 x 为根的集合大小
UnionFind(int n) : parent(n), sz(n, 1) {
    iota(parent.begin(), parent.end(), 0);
}
void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;               // 已同集合
    if (sz[rx] < sz[ry]) swap(rx, ry);  // 保证 rx 是较大的树
    parent[ry] = rx;                    // 小树挂到大树下
    sz[rx] += sz[ry];                   // 更新集合大小
}

按秩合并（rank 为树高上界，便于理论分析）：

vector<int> parent, rank_;              // rank_[x]：以 x 为根的树高上界
UnionFind(int n) : parent(n), rank_(n, 0) {
    iota(parent.begin(), parent.end(), 0);
}
void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;               // 已同集合
    if (rank_[rx] < rank_[ry]) swap(rx, ry);  // 保证 rx 秩不更低
    parent[ry] = rx;                    // 矮树挂到高树下
    if (rank_[rx] == rank_[ry]) rank_[rx]++;  // 秩相同则新根秩加一
}

复杂度：阿克曼反函数

两者组合均摊 $O(\alpha(n))$ 。 $\alpha(n)$ 增长极慢，任何实际规模下 $\alpha(n) \le 5$ ，可视为常数。

$n$	$\alpha(n)$
$\le 16$	$\le 2$
$\le 10^{80}$	$\le 4$

注意： $O(\alpha(n))$ 为均摊复杂度，单次最坏仍可达 $O(\log n)$ 。需严格单次保证或可持久化时，只能用按秩合并不做路径压缩。

完整模板

同时启用路径压缩与按大小合并，附带连通分量计数与集合大小查询：

struct UnionFind {
    vector<int> parent, sz;  // parent[x]：父节点；sz[x]：以 x 为根的集合大小
    int components;          // 当前连通分量（独立集合）数量
    explicit UnionFind(int n) : parent(n), sz(n, 1), components(n) {
        iota(parent.begin(), parent.end(), 0);  // 初始各自成集合
    }
    int find(int x) {                   // 路径压缩版查找
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);  // 沿途节点直接挂到根下
    }

    bool unite(int x, int y) {          // 合并；返回 false 表示本就同集合
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (sz[rx] < sz[ry]) swap(rx, ry);  // 保证 rx 是较大的树
        parent[ry] = rx;                // 小树挂大树
        sz[rx] += sz[ry];
        --components;                   // 连通分量减一
        return true;
    }
    
    bool connected(int x, int y) {      // 查询是否同集合
        return find(x) == find(y);
    }

    int size(int x) { return sz[find(x)]; }  // x 所在集合的大小
};

要点：

下标：模板 0-indexed；题目 1-indexed 时开 $n+1$ 大小或调用时 -1。
unite 返回值：false 表示本就同集合——判环时有用。
非整数元素：字符串等先用哈希表映射为整数编号。
连通分量计数：初始 $n$ ，每次成功 unite 减一。

全局数组写法（竞赛常用）

固定上界 + 全局数组 + 自由函数，书写最短、规模再大也不爆栈，是竞赛最常见写法：

const int N = 1e5 + 10;                 // 须大于数据规模上限
int fa[N], sz[N], cnt;                  // fa：父节点；sz：集合大小；cnt：连通分量数

void init(int n) {
  cnt = n;                              // 初始 n 个独立集合
  for (int i = 0; i < n; ++i) {
    fa[i] = i;                          // 各自为根
    sz[i] = 1;
  }
}

int find(int x) {                       // 路径压缩版查找
  return fa[x] == x ? x : fa[x] = find(fa[x]);
}

bool unite(int x, int y) {              // 合并；返回 false 表示已同集合
  int rx = find(x), ry = find(y);
  if (rx == ry) return false;
  if (sz[rx] < sz[ry]) swap(rx, ry);    // 保证 rx 是较大的树
  fa[ry] = rx;                          // 小树挂大树
  sz[rx] += sz[ry];
  --cnt;                                // 连通分量减一
  return true;
}

bool connected(int x, int y) {          // 查询是否同集合
  return find(x) == find(y);
}

与类模板一一对应：fa↔parent、sz↔siz、cnt↔components，init 充当构造函数；集合大小直接读 sz[find(x)]，无需再封装。注意 N 须大于数据规模上限，多组数据时每次重新 init，否则残留状态会污染结果。

经典示例

连通分量计数与无向图判环

逐条加边 unite，unite 返回 false 则成环，最终 components 即连通分量数。

int main() {
    int n, m;
    scanf("%d%d", &n, &m);              // n 个点，m 条边
    UnionFind uf(n);
    bool hasCycle = false;
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        if (!uf.unite(u, v)) hasCycle = true;  // 两端已连通，加入此边即成环
    }
    printf("%d\n", uf.components);      // 连通分量数
    printf("%s\n", hasCycle ? "YES" : "NO");   // 是否存在环
}

并查集判环仅适用于无向图。有向图用 DFS 三色标记或拓扑排序。

冗余连接（LeetCode 684）

树多加一条边形成唯一环，按输入顺序逐条 unite，第一条返回 false 的边即冗余边。

vector<int> findRedundantConnection(
    vector<vector<int>>& edges) {
    UnionFind uf(edges.size() + 1);     // 节点编号 1..n，多开一位
    for (auto& e : edges)
        if (!uf.unite(e[0], e[1])) return e;  // 第一条使两端已连通的边即冗余边
    return {};
}

等式方程可满足性（LeetCode 990）

先处理等、再查不等：第一趟合并所有 ==，第二趟检查 != 两端是否已连通。

bool equationsPossible(vector<string>& eqs) {
    UnionFind uf(26);                   // 26 个小写字母各为一个元素
    for (auto& s : eqs)                 // 第一趟：合并所有相等约束
        if (s[1] == '=') uf.unite(s[0]-'a', s[3]-'a');
    for (auto& s : eqs)                 // 第二趟：检查不等约束
        if (s[1] == '!' &&
            uf.connected(s[0]-'a', s[3]-'a'))
            return false;               // 要求不等的两端已被判相等，矛盾
    return true;
}

账户合并（LeetCode 721）

元素为邮箱（字符串），先哈希映射为整数编号，每个账户内首个邮箱与其余 unite，按根分组输出。

vector<vector<string>> accountsMerge(
    vector<vector<string>>& accounts) {
    unordered_map<string, int> emailId;   // 邮箱 -> 整数编号
    unordered_map<int, string> idToEmail; // 编号 -> 邮箱
    vector<string> idName;                // 编号 -> 账户名
    int idx = 0;
    for (auto& acc : accounts)           // 为每个出现过的邮箱分配唯一编号
        for (int i = 1; i < acc.size(); ++i)
            if (!emailId.count(acc[i])) {
                emailId[acc[i]] = idx;
                idToEmail[idx] = acc[i];
                idName.push_back(acc[0]);
                idx++;
            }
    UnionFind uf(idx);
    for (auto& acc : accounts) {         // 同账户内的邮箱彼此连通
        int first = emailId[acc[1]];    // 以首个邮箱为代表
        for (int i = 2; i < acc.size(); ++i)
            uf.unite(first, emailId[acc[i]]);
    }
    unordered_map<int, vector<string>> groups;  // 根 -> 该集合所有邮箱
    for (int i = 0; i < idx; ++i)
        groups[uf.find(i)].push_back(idToEmail[i]);
    vector<vector<string>> ans;
    for (auto& [root, emails] : groups) {
        sort(emails.begin(), emails.end());    // 邮箱按字典序排列
        vector<string> account;
        account.push_back(idName[root]);       // 首元素为账户名
        account.insert(account.end(),
            emails.begin(), emails.end());
        ans.push_back(move(account));
    }
    return ans;
}

Kruskal 最小生成树

边按权升序排序，逐条考察：unite 返回 true 则加入生成树，选够 $n-1$ 条即得 MST。

struct Edge { int u, v, w; };           // 无向边：两端点与权值
int kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(),    // 按权值升序
         [](auto& a, auto& b){ return a.w < b.w; });
    UnionFind uf(n);
    int total = 0, cnt = 0;             // total：MST 权值和；cnt：已选边数
    for (auto& e : edges) {
        if (uf.unite(e.u, e.v)) {       // 两端原本不连通，加入不成环
            total += e.w;
            if (++cnt == n - 1) break;  // 选够 n-1 条边即成树
        }
    }
    return total;
}

复杂度 $O(m\log m)$ 。并查集在此扮演「动态维护连通分量、快速判环」的角色。

岛屿数量（LeetCode 200）

每个陆地格子与左、上邻居若是陆地则 unite，二维坐标压成一维 $i\cdot n+j$ 。

int numIslands(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size();
    UnionFind uf(m * n);                // 每个格子一个元素
    int land = 0, merged = 0;           // land：陆地块数；merged：成功合并次数
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (grid[i][j] == '1') {
                ++land;
                int id = i * n + j;     // 二维坐标压成一维编号
                if (i > 0 && grid[i-1][j] == '1' &&   // 与上方陆地合并
                    uf.unite(id, (i-1)*n+j))
                    ++merged;
                if (j > 0 && grid[i][j-1] == '1' &&   // 与左方陆地合并
                    uf.unite(id, i*n+(j-1)))
                    ++merged;
            }
    return land - merged;  // 陆地数 - 合并次数 = 连通分量数
}

带权并查集

元素间携带关系或权值（差值、奇偶、倍数等）时，每个节点额外维护 w[x] 表示 $x$ 到 parent[x] 的权值，在路径压缩与合并时同步更新。权值须可沿路径复合（加法、异或等）。

通用模板（加法权值）

struct WeightedUnionFind {
    vector<int> parent, w;  // w[x]: x 到 parent[x] 的权值
    explicit WeightedUnionFind(int n) : parent(n), w(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] == x) return x;
        int root = find(parent[x]);
        // x 到 root = x 到旧 parent + 旧 parent 到 root
        w[x] += w[parent[x]];
        parent[x] = root;
        return root;
    }
    // 建立 x -> y 权值为 val 的关系
    void unite(int x, int y, int val) {
        int rx = find(x), ry = find(y);
        // 已同集合：可校验 w[x]-w[y] 是否等于 val
        if (rx == ry) return;
        parent[rx] = ry;
        // 由 x 到 y 权值为 val 反解
        w[rx] = val - w[x] + w[y];
    }
};

关键：unite 中固定 parent[rx]=ry 后，由「 $x$ 到 $y$ 的累计权值等于 val」反解 w[rx]。掌握该推导即可处理各类变体，无需死记公式。

校验合法性：find(x)==find(y) 时， $x$ 到 $y$ 的权值 $=w[x]-w[y]$ ，与给定关系矛盾则不可满足。

食物链（NOI / POJ 1182）

$N$ 个动物构成 A→B→C→A 环形食物链。给定 $K$ 句话（同类/吃），判断多少句是假话。

用模 3 权值 $w[x]\in\{0,1,2\}$ ： $0$ 同类、 $1$ $x$ 吃 parent、 $2$ $x$ 被 parent 吃。复合关系是模 3 加法。 $x,y$ 同集合时， $x$ 对 $y$ 的关系 $=(w[x]-w[y])\bmod 3$ 。

int parent[MAXN], w[MAXN];              // w[x]：x 相对父节点的关系（模 3）
int find(int x) {
    if (parent[x] == x) return x;
    int root = find(parent[x]);         // 先递归更新父节点的权值
    w[x] = (w[x] + w[parent[x]]) % 3;   // 再累加得到 x 相对根的关系
    parent[x] = root;
    return root;
}
int main() {
    int N, K;
    scanf("%d%d", &N, &K);
    iota(parent+1, parent+N+1, 1);      // 1-indexed 初始化
    fill(w+1, w+N+1, 0);
    int fake = 0;                       // 假话计数
    while (K--) {
        int d, x, y;
        scanf("%d%d%d", &d, &x, &y);    // d=1 同类；d=2 表示 x 吃 y
        if (x > N || y > N || (d == 2 && x == y)) {  // 编号越界或自己吃自己
            ++fake;
            continue;
        }
        int rx = find(x), ry = find(y);
        if (rx == ry) {                 // 已同集合：校验与已有关系是否矛盾
            if ((w[x] - w[y] + 3) % 3 != d - 1) ++fake;
        } else {                        // 不同集合：按给定关系合并
            parent[rx] = ry;
            w[rx] = ((d - 1) - w[x] + w[y] + 3) % 3;  // 反解 rx 相对 ry 的权值
        }
    }
    printf("%d\n", fake);
}

扩展域并查集（种类并查集）

另一条路线：将每个元素拆为 $k$ 个虚拟节点，用基础并查集维护等价关系。以食物链为例， $x$ 拆为 $x$ （同类域）、 $x+N$ （猎物域）、 $x+2N$ （天敌域）。「 $x,y$ 同类」合并 $x\leftrightarrow y$ 、 $x+N\leftrightarrow y+N$ 、 $x+2N\leftrightarrow y+2N$ ；「 $x$ 吃 $y$ 」合并 $x\leftrightarrow y+N$ 、 $x+N\leftrightarrow y+2N$ 、 $x+2N\leftrightarrow y$ 。

优势：仅需基础并查集，无需维护权值；代价是节点数扩大 $k$ 倍。两种方案等价，按空间与习惯选择。

关押罪犯（NOIP 2010）

$N$ 个罪犯分押两座监狱， $M$ 对冲突各有影响力，求合理分配使最大冲突影响力最小。

利用「敌人的敌人是朋友」：每个罪犯 $x$ 拆为 $x$ （自身域）与 $x+N$ （敌人域）。冲突按影响力降序处理：若 find(a)==find(b) 则该冲突无法避免，输出其影响力；否则合并 $a$ 与 $b+N$ 、 $b$ 与 $a+N$ 。

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    vector<array<int,3>> e(M);          // {a, b, c}：a、b 冲突，影响力 c
    for (auto& [a,b,c] : e)
        scanf("%d%d%d", &a, &b, &c);
    sort(e.begin(), e.end(),            // 按影响力从大到小，优先化解大冲突
         [](auto& x, auto& y){ return x[2] > y[2]; });
    UnionFind uf(2 * N + 1);            // x：自身域；x+N：敌人域
    int ans = 0;
    for (auto& [a,b,c] : e) {
        if (uf.find(a) == uf.find(b)) { // a、b 被迫同狱，冲突无法避免
            ans = c;                    // 第一个无法避免的即最大影响力
            break;
        }
        uf.unite(a, b + N);             // a 与 b 的敌人同狱
        uf.unite(b, a + N);             // b 与 a 的敌人同狱
    }
    printf("%d\n", ans);                // 全部可化解则输出 0
}

可撤销并查集

路径压缩破坏中间结构无法回退。放弃路径压缩、仅用按秩合并，则每次 unite 仅修改一个 parent 与至多一个 rank——记录修改即可按序回退，单次 $O(\log n)$ 。

struct RollbackUnionFind {
    vector<int> p, r;
    vector<pair<int,int>> hist;  // 修改历史：(下标, 旧值)，负值表示 rank 修改
    RollbackUnionFind(int n) : p(n), r(n, 0) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {                   // 不做路径压缩，保证可回退
        while (p[x] != x) x = p[x];
        return x;
    }
    bool unite(int a, int b) {          // 仅按秩合并
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (r[a] < r[b]) swap(a, b);    // 保证 a 秩不更低
        hist.push_back({b, p[b]});      // 记录 parent 旧值
        p[b] = a;
        if (r[a] == r[b]) {
            hist.push_back({a, ~r[a]}); // 取反（负值）标记这是 rank 修改
            r[a]++;
        }
        return true;
    }
    int snapshot() { return hist.size(); }  // 记录当前历史长度作为快照
    void rollback(int snap) {           // 回退到快照时刻
        while (hist.size() > snap) {
            auto [i, old] = hist.back();
            hist.pop_back();
            if (old < 0) r[i] = ~old;   // 负值：恢复 rank
            else p[i] = old;            // 非负：恢复 parent
        }
    }
};

核心应用：离线分治。典型场景为动态连通性——边随时间加入与删除，在时间轴上构建线段树分治，递归时 unite、回溯时 rollback， $O(m\log T\cdot\log n)$ 。

可撤销并查集不得与路径压缩混用。

横向对比

场景	并查集	DFS/BFS	其他
静态图连通分量	$O(m\alpha)$	$O(n+m)$	两者皆可，DFS 更直观
动态加边、查连通	$O(\alpha)$ /次，最优	每次重遍历 $O(n+m)$	LCT 常数极大
判无向图环	$O(m\alpha)$	$O(n+m)$	拓扑排序仅适用有向图
动态连通性（含删边）	可撤销 + 离线分治	不适用	LCT $O(m\log n)$ 在线
MST	Kruskal $O(m\log m)$	Prim $O(m\log n)$	各有适用场景
带关系约束的分组	带权/扩展域	不自然	2-SAT 也可处理部分
路径还原	不能	可记前驱	用 BFS/Dijkstra

判别要点：

连通性 vs 路径：并查集只判连通，无法给出具体路径。
静态 vs 动态：图完全给定时 DFS/BFS 一次即可；需逐条加边并随时查询时并查集几乎唯一选择。
在线 vs 离线：需删边/撤销，在线只能 LCT；允许离线则可撤销并查集 + 分治更轻量。

常见陷阱

未初始化 parent[x]=x：vector 默认全 0，find 死循环。
路径压缩与可撤销混用：撤销无法正确恢复中间结构。
按秩合并时 rank 失真：路径压缩使实际树高小于 rank，但不影响正确性——rank 仅为上界，无需修正。
0-indexed 与 1-indexed 混淆：开 $n+1$ 大小或调用时 -1。
合并方向未约束：必须配合按秩或按大小合并，否则可退化为链。
unite 后忘记更新附加信息：components、size 仅在 rx!=ry 时更新。
带权并查集 find 顺序错误：必须先递归更新 w[parent[x]]，再更新 w[x]。
关系编码方向不一致：权值符号与域的选择必须全文统一。
字符串元素直接用作数组下标：必须先哈希映射为整数编号。
判环只判无向图：有向图用 DFS 三色标记或拓扑排序。
以为并查集能求最短路：只维护连通，不维护距离。

小结

并查集以森林表示互不相交的集合族，路径压缩（查询时扁平化）与按秩/按大小合并（小树挂大树）将单次操作均摊至 $O(\alpha(n))$ 。变体覆盖「动态维护分组与关系」大类问题：

识别：动态加边 + 连通查询、等价类划分、关系约束 → 优先考虑并查集。
选型：仅需连通性 → 基础并查集；带关系约束 → 带权或扩展域；需撤销 → 可撤销（禁用路径压缩）。
推导：带权并查集的合并权值由「 $x$ 到 $y$ 累计权值等于 val」现场反解，掌握推导即可处理任意变体。