并查集

概念讲解

什么是并查集？

并查集是一种处理不相交集合的合并与查询问题的数据结构。

基本操作

操作 说明
Find 查找元素所属集合
Union 合并两个集合

基础实现

路径压缩

123456789101112131415const int N = 100005;
int parent[N];

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

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

void unite(int x, int y) {
    parent[find(x)] = find(y);
}

按秩合并

123456789int rank[N];

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);
    parent[ry] = rx;
    if (rank[rx] == rank[ry]) rank[rx]++;
}

时间复杂度

操作 时间复杂度
find O(α(n)) ≈ O(1)
unite O(α(n)) ≈ O(1)

α 是反阿克曼函数，几乎为常数。

应用

  1. 判断连通性
  2. 最小生成树（Kruskal）
  3. 集合合并

考点分析

初赛考查方式

  1. 程序阅读： 并查集操作
  2. 编程题： 连通性问题

常见考点

  • 路径压缩
  • 按秩合并
  • 连通块计数

例题精讲

例题 1：连通块

题目： 判断两个点是否连通。

解答：

123if (find(x) == find(y)) {
    cout << "连通" << endl;
}

练习题

  1. 路径压缩的作用是什么？
查看答案

路径压缩的作用是降低树的高度，使 find 操作更快。

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

路径压缩后，树的高度几乎为 2，find 操作接近 O(1)。

  1. 按秩合并的作用是什么？
查看答案

按秩合并的作用是保持树的平衡，避免退化成链。

1234567void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rank[rx] < rank[ry]) swap(rx, ry);
    parent[ry] = rx;
    if (rank[rx] == rank[ry]) rank[rx]++;
}

总是将小树合并到大树上。

  1. 并查集的时间复杂度是多少？
查看答案

并查集的时间复杂度：

  • find：O(α(n))≈O(1)O(\alpha(n)) \approx O(1)
  • unite：O(α(n))≈O(1)O(\alpha(n)) \approx O(1)

其中 α\alpha 是反阿克曼函数，几乎为常数。

易错点

⚠️ 注意：

  1. 初始化时 parent[i] = i
  2. find 要路径压缩
  3. unite 前要判断是否已连通
  4. 按秩合并可以进一步优化