InoueMoby's Blog

前言：“你们是不是一伙的？”

想象一个社交网络：一开始每个人都是孤立的。然后不断有人建立好友关系——A 和 B 成了好友，C 和 D 成了好友，B 和 C 成了好友。这时候你需要回答一个问题：A 和 D 是不是在同一个朋友圈里？

朴素做法：每次问的时候，从 A 出发做一次 BFS/DFS，看能不能走到 D。但好友关系可能有 $10^6$ 条，查询也有 $10^6$ 次，每次都 BFS 的话总共 $10^{12}$ ——不行。

关键观察：我们不需要知道 A 到 D 的路径是什么，只需要知道它们是否连通。这比维护完整路径简单得多。

并查集就是为这种”合并集合 + 查询是否同属一个集合”量身打造的数据结构。每个集合是一棵树，树根就是集合的”代表元”。查询时沿着父指针走到根就知道自己是哪个集合的；合并时把一棵树的根挂到另一棵上就行。

加上两个优化（路径压缩 + 按秩合并），每次操作几乎是 $O(1)$ 。 $10^6$ 次操作，瞬间跑完。

并查集

问题的本质

动态维护若干个不相交集合，支持两种操作：

合并（Union）：把两个集合合成一个
查询（Find）：某个元素属于哪个集合（通常用集合的”代表元”标识）

朴素做法：数组 belong[i] 记录元素 $i$ 属于哪个集合。Find $O(1)$ ，但 Union 需要遍历整个数组修改， $O(n)$ 。 $m$ 次操作最坏 $O(nm)$ 。

关键洞察：用树来组织集合——每个集合是一棵树，根就是代表元。Find 就是沿着父指针走到根，Union 就是把一棵树的根挂到另一棵树上。

基本实现

int parent[MAXN];

void init(int n) {
    for (int i = 0; i < n; i++) parent[i] = i;  // 初始各自为根
}

int find(int x) {
    if (parent[x] != x)
        return find(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 的根下
}

问题：链式退化为 $O(n)$ 的 Find。

路径压缩

Find 的时候顺便把路径上所有节点直接接到根上——下次再查就是 $O(1)$ 。

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);  // 压缩：直接指向根
    return parent[x];
}

按秩合并

合并时把矮树挂到高树下，避免树越来越高。用 rank 数组记录树的高度：

int parent[MAXN], rnk[MAXN];

void init(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rnk[i] = 0;
    }
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rnk[rx] < rnk[ry]) parent[rx] = ry;
    else if (rnk[rx] > rnk[ry]) parent[ry] = rx;
    else { parent[ry] = rx; rnk[rx]++; }
}

两者结合后， $m$ 次操作的均摊复杂度为 $O(m \cdot \alpha(n))$ ，其中 $\alpha$ 是反阿克曼函数，对任何实际规模 $\alpha(n) < 5$ ，实质上是常数。

例题：朋友圈

有 $n$ 个人和 $m$ 条关系，每条关系说明两个人是朋友（朋友关系传递）。最后有 $q$ 次询问，每次问两个人是否在同一个朋友圈里。

$1 \le n, q \le 10^6$ ， $1 \le m \le 10^6$

每个人是一个元素，朋友关系就是合并操作，询问就是查询是否同属一个集合。

#include <cstdio>
using namespace std;

const int MAXN = 1000006;
int parent[MAXN], rnk[MAXN];

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

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rnk[rx] < rnk[ry]) parent[rx] = ry;
    else if (rnk[rx] > rnk[ry]) parent[ry] = rx;
    else { parent[ry] = rx; rnk[rx]++; }
}

int main() {
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) { parent[i] = i; rnk[i] = 0; }

    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        unite(u, v);
    }

    while (q--) {
        int u, v;
        scanf("%d%d", &u, &v);
        printf(find(u) == find(v) ? "Yes\n" : "No\n");
    }
    return 0;
}

解析： $m$ 次 Union + $q$ 次 Find，每次均摊 $O(\alpha(n)) \approx O(1)$ ，总量线性。并查集天然适合处理”连通性”问题——不需要知道具体的连通路径，只需要知道”是否连通”。如果需要路径信息，就该换 BFS/DFS 了。

并查集

维护不相交集合的合并与查询