并查集

想象你在一个万人的社交网络里，不断有人添加好友、建立联系。每时每刻都有人在问："我和某个人是不是在同一个朋友圈里？"

朋友圈的关系是传递的——如果 A 和 B 是好友，B 和 C 是好友，那么 A 和 C 也在同一个圈子里。这本质上是一个 动态连通性（Dynamic Connectivity） 问题：元素不断合并成集合，同时需要快速查询两个元素是否属于同一个集合。

暴力做法？每次查询遍历整个图——$O(n)$ 甚至更差。但如果我告诉你，存在一种数据结构，可以让每次操作的时间复杂度降到 近乎常数，你会不会觉得不可思议？

这就是并查集（Union-Find），也叫不相交集合（Disjoint Set Union, DSU）。它只提供两个操作，却足以解决一类非常广泛的问题。

并查集的核心表示是森林（Forest）——每一棵树代表一个集合，树的根节点就是这个集合的"代表元"。

具体实现非常朴素：用一个数组 parent[]，其中 parent[i] 表示节点 i 的父节点。如果 parent[i] == i，那么 i 就是根。

来写一个最朴素的版本：

int parent[MAXN];

// 初始化：每个元素自成一个集合
void init(int n) {
    for (int i = 0; i < n; i++)
        parent[i] = i;
}

// 查找根
int find(int x) {
    while (parent[x] != x)
        x = parent[x];
    return x;
}

// 合并
void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry)
        parent[rx] = ry;  // 把 x 的根挂到 y 的根下面
}

思路非常直觉：在查找的过程中，顺手把沿途经过的所有节点都直接接到根上。就像你每次问路，不仅自己记住了怎么走，还把沿途所有路标都改成了直达终点的方向。

这只需在 Find 里加一行递归：

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);  // 路径压缩
    return parent[x];
}

每一次 Find 调用后，从查询节点到根的路径上的所有节点，都会变成根的直接子节点。树的形态从一条长链"压扁"成了一个几乎只有两层的矮树。

路径压缩解决了"查询后树变矮"的问题，但第一次查询之前呢？如果初始时树就已经很高了，第一次 Find 还是慢。

按秩合并（Union by Rank）的思路是：在合并两棵树时，总是把较矮的树挂到较高的树下面。这样树的高度永远不会无意义地增长。

用 rank[] 数组记录每棵根节点树的高度上界：

int parent[MAXN], rnk[MAXN];

void init(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rnk[i] = 0;  // 初始高度为 0
    }
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;          // 已经在同一集合
    if (rnk[rx] < rnk[ry])         // x 的树更矮
        parent[rx] = ry;           // 把矮树挂到高树下
    else if (rnk[rx] > rnk[ry])
        parent[ry] = rx;
    else {
        parent[ry] = rx;           // 等高时任选一个
        rnk[rx]++;                 // 高度 +1
    }
}

当路径压缩 + 按秩合并同时使用时，$m$ 次操作（Find 和 Union 的混合）在 $n$ 个元素上的总时间复杂度为：

$O(m \cdot \alpha(n))$

其中 $\alpha(n)$ 是反阿克曼函数（Inverse Ackermann Function）。这个函数增长得极其缓慢——对于任何实际可能遇到的 $n$（哪怕 $n = 2^{2^{2^{65536}}}$），$\alpha(n)$ 都不会超过 4。

可以认为，在实际应用中，并查集的每次操作就是 $O(1)$ 的。

标准并查集只关心"在不在同一个集合"。但如果我们在 parent 的边上附加一些额外信息呢？

带权并查集（Weighted Union-Find）在每条边 $(x, \text{parent}[x])$ 上存储一个权重。在路径压缩时，权重需要按规则累加；在合并时，需要根据关系计算新边的权重。

经典应用是食物链问题（POJ 1182）：有 A、B、C 三种动物，A 吃 B，B 吃 C，C 吃 A。给出若干条"X 吃 Y"或"X 和 Y 同类"的陈述，判断哪些是谎言。

// parent[x]: x 的父节点
// weight[x]: x 到 parent[x] 的关系权重 (0=同类, 1=被吃, 2=吃)
int parent[MAXN], weight[MAXN];

int find(int x) {
    if (parent[x] != x) {
        int root = find(parent[x]);
        weight[x] = (weight[x] + weight[parent[x]]) % 3;  // 路径压缩时累加权重
        parent[x] = root;
    }
    return parent[x];
}

关键在于合并时的关系推导——已知 $x$ 和 $y$ 的关系，以及它们到各自根的关系，要推出两棵树的根之间的关系。这需要一点模运算的推导。

下面是一个完整的、带路径压缩和按秩合并的并查集模板，适用于大多数竞赛场景：

#include <vector>
using namespace std;

struct DSU {
    vector<int> parent, rnk, sz;

    DSU(int n) : parent(n), rnk(n, 0), sz(n, 1) {
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;      // 已经在同一集合
        if (rnk[x] < rnk[y]) swap(x, y);
        parent[y] = x;                 // y 挂到 x 下面
        sz[x] += sz[y];                // 维护集合大小
        if (rnk[x] == rnk[y]) rnk[x]++;
        return true;
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return sz[find(x)];
    }
};

用法示例——判断图中的连通分量数：

int countComponents(int n, vector<pair<int,int>>& edges) {
    DSU dsu(n);
    int components = n;
    for (auto [u, v] : edges) {
        if (dsu.unite(u, v))  // 成功合并说明减少了一个连通分量
            components--;
    }
    return components;
}

并查集不是万能的，但在以下场景中它是首选：