基础并查集（Union-Find）详解（含两大核心优化）

并查集是一种高效维护集合连通性的数据结构，核心解决“判断元素是否同属一个集合”“合并两个集合”两类问题，下面从基础逻辑到两大优化进行拆解。

一、并查集核心概念

1. 核心操作

• 查（Find）：找到某个元素所属集合的“根节点”（集合的唯一标识）；
• 并（Union）：将两个元素所在的集合合并为一个。

2. 核心思想

用数组 parent[] 记录每个元素的父节点，初始时每个元素的父节点是自身（各自成独立集合）；通过 find 找根、union 合并根，实现集合管理。

二、基础版并查集（无优化）

先实现最朴素的版本，理解核心逻辑，再看优化的必要性。

代码实现

#include <iostream>
using namespace std;

const int MAXN = 1e5 + 7;
int parent[MAXN]; // parent[i]：元素i的父节点

// 初始化：每个元素自成一个集合
void init(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i; // 父节点指向自己
    }
}

// 查找：找元素x的根节点（无优化）
int find(int x) {
    if (parent[x] != x) { // 不是根节点，递归找父节点
        return find(parent[x]);
    }
    return x; // 根节点返回自身
}

// 合并：合并x和y所在的集合（无优化）
void merge(int x, int y) {
    int fx = find(x); // x的根
    int fy = find(y); // y的根
    if (fx != fy) {   // 不同集合才合并
        parent[fy] = fx; // 直接将fy挂到fx下（无策略）
    }
}

int main() {
    int n = 5;
    init(n);
    merge(1, 2);
    merge(2, 3);
    // 判断1和3是否连通
    cout << (find(1) == find(3) ? "连通" : "不连通") << endl; // 输出：连通
    return 0;
}

基础版的问题

• 查找效率低：若形成链式结构（如 1→2→3→4→根），每次 find 需递归到底，时间复杂度O(n)；
• 合并无策略：随意将一个集合挂到另一个集合下，易形成高树，进一步降低查找效率。

三、优化1：路径压缩（Find操作优化）

核心思想

查找元素的根节点时，将路径上所有节点的父节点直接指向根节点，扁平化树结构，让后续查找一步到位。

代码实现（仅修改find函数）

// 查找：带路径压缩
int find(int x) {
    if (parent[x] != x) {
        // 路径压缩：递归时直接将x的父节点设为根节点
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

效果演示

原路径：1→2→3→4（根）
执行 find(1) 后：1的父节点→4、2的父节点→4、3的父节点→4
后续查找1/2/3时，直接指向根4，时间复杂度从O(n)降至近似O(1)。

四、优化2：按秩合并（Union操作优化）

“秩”可选择集合大小或树的高度，核心是：将小集合/矮树合并到大集合/高树上，避免树的高度过高。

方式1：按集合大小合并（更常用）

代码实现

#include <iostream>
#include <algorithm> // swap
using namespace std;

const int MAXN = 1e5 + 7;
int parent[MAXN];
int sz[MAXN]; // sz[i]：以i为根的集合的大小

// 初始化：集合大小初始为1
void init(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        sz[i] = 1;
    }
}

// 带路径压缩的find（同优化1）
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[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);
    parent[fy] = fx;       // 把fy挂到fx上
    sz[fx] += sz[fy];      // 大集合大小 += 小集合大小
}

方式2：按树的高度合并

代码实现

#include <iostream>
#include <algorithm> // swap
using namespace std;

const int MAXN = 1e5 + 7;
int parent[MAXN];
int rank_[MAXN]; // rank_[i]：以i为根的树的高度（避免与关键字rank重名）

// 初始化：树高初始为1
void init(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        rank_[i] = 1;
    }
}

// 带路径压缩的find（同优化1）
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// 合并：按树高合并
void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    
    // 矮树合并到高树下
    if (rank_[fx] < rank_[fy]) swap(fx, fy);
    parent[fy] = fx;
    // 仅当两棵树高度相同时，合并后高度+1
    if (rank_[fx] == rank_[fy]) rank_[fx]++;
}

效果演示

集合A大小为5，集合B大小为3：

• 按大小合并：将B挂到A下，树高不变；
• 若反向合并：A挂到B下，树高会显著增加，查找效率降低。

五、完整优化版并查集模板（必背）

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 7;
int parent[MAXN]; // 父节点数组
int sz[MAXN];     // 集合大小（按大小合并）

// 初始化
void init(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        sz[i] = 1;
    }
}

// 查找：路径压缩
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[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);
    parent[fy] = fx;
    sz[fx] += sz[fy];
}

// 辅助函数：判断x和y是否连通
bool isConnected(int x, int y) {
    return find(x) == find(y);
}

// 示例使用
int main() {
    int n = 5, m = 3;
    init(n);
    merge(1, 2);
    merge(2, 3);
    merge(4, 5);
    
    cout << isConnected(1, 3) << endl; // 1（连通）
    cout << isConnected(1, 4) << endl; // 0（不连通）
    return 0;
}

六、核心总结

1. 两个优化结合使用，时间复杂度接近O(1)（严格为阿克曼函数的反函数，比O(logn)更优）；
2. 基础并查集的核心是“找根+合并根”，优化的本质是降低树的高度；