并查集

算法概述

【并查集】是一种树形数据结构，用于处理一些不相交集合的合并及查询问题。主要支持两种操作：

• 查找（Find）：确定元素属于哪一个子集
• 合并（Union）：将两个子集合并成一个集合

算法设计思路

并查集主要用于解决连接性问题，如"网络中节点A和节点B是否连通"等。它的核心思想是：

1. 每个集合用一棵树表示，树中的节点表示元素
2. 树的根节点作为集合的代表元素
3. 通过"压缩"查找路径和"按秩合并"来优化操作效率

代码实现与解析

基本并查集实现

// 初始化并查集，parent[i] = i 表示每个元素初始时都是独立的集合
void init(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i; // 每个节点的父节点初始为自己
    }
}

// 查找操作 - 寻找元素x所属集合的代表元素
int find(int x) {
    if (parent[x] == x) return x; // 如果x是根节点，则返回x
    return find(parent[x]); // 递归查找x的父节点
}

// 合并操作 - 将元素x所在集合与元素y所在集合合并
void union_sets(int x, int y) {
    int root_x = find(x); // 找到x的根节点
    int root_y = find(y); // 找到y的根节点

    if (root_x != root_y) {
        parent[root_x] = root_y; // 将x的根节点指向y的根节点
    }
}

优化后的并查集实现

// 初始化带秩的并查集
void init(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 1; // 初始化每个节点的秩为1
    }
}

// 路径压缩优化的查找操作
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩：直接指向根节点
    }
    return parent[x];
}

// 按秩合并优化的合并操作
void union_sets(int x, int y) {
    int root_x = find(x);
    int root_y = find(y);

    if (root_x == root_y) return; // 已经在同一集合中

    // 按秩合并：将较小的树连接到较大的树下
    if (rank[root_x] < rank[root_y]) {
        parent[root_x] = root_y;
    } else if (rank[root_x] > rank[root_y]) {
        parent[root_y] = root_x;
    } else {
        parent[root_y] = root_x;
        rank[root_x]++; // 秩相同时，新树的秩加1
    }
}

逻辑图解

初始状态: [1] [2] [3] [4] [5]  (5个独立元素)
执行union(1,2): [1,2] [3] [4] [5]
执行union(3,4): [1,2] [3,4] [5]
执行union(1,3): [1,2,3,4] [5]

复杂度分析

• 时间复杂度:
  • 未优化时：查找操作O(n)，合并操作O(n)
  • 路径压缩+按秩合并后：均摊近乎O(1)，严格来说是O(α(n))，α是阿克曼函数的反函数，在实际使用中可视为常数
• 空间复杂度: O(n) 存储父节点数组和秩数组

典型应用场景

1. 判断网络连接性问题
2. 最小生成树的Kruskal算法
3. 等价类划分
4. 动态连通性问题

典型例题分析

例题：朋友圈问题

有n个人，给出他们之间的朋友关系，求朋友圈的数量（朋友的朋友也是朋友）。

int findCircleNum(vector<vector<int>>& M) {
    int n = M.size();
    vector<int> parent(n);
    vector<int> rank(n, 1);

    // 初始化并查集
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    // 合并朋友关系
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (M[i][j] == 1) {
                union_sets(parent, rank, i, j);
            }
        }
    }

    // 计算朋友圈数量
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (parent[i] == i) { // 根节点的数量就是集合的数量
            count++;
        }
    }
    return count;
}

// 查找函数
int find(vector<int>& parent, int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]); // 路径压缩
    }
    return parent[x];
}

// 合并函数
void union_sets(vector<int>& parent, vector<int>& rank, int x, int y) {
    int root_x = find(parent, x);
    int root_y = find(parent, y);

    if (root_x == root_y) return;

    // 按秩合并
    if (rank[root_x] < rank[root_y]) {
        parent[root_x] = root_y;
    } else if (rank[root_x] > rank[root_y]) {
        parent[root_y] = root_x;
    } else {
        parent[root_y] = root_x;
        rank[root_x]++;
    }
}

易错点与调试技巧

1. 【路径压缩】是关键优化，不使用可能导致树非常高

   // 错误写法（没有路径压缩）
   int find(int x) {
       if (parent[x] == x) return x;
       return find(parent[x]); // 没有更新parent[x]
   }
   
   // 正确写法
   int find(int x) {
       if (parent[x] != x) {
           parent[x] = find(parent[x]); // 路径压缩
       }
       return parent[x];
   }
   

2. 【按秩合并】对性能也很重要

   // 不加判断的合并可能导致树很高
   void union_wrong(int x, int y) {
       int root_x = find(x);
       int root_y = find(y);
       parent[root_x] = root_y; // 总是将x连到y下，可能导致很高的树
   }
   

练习题推荐

1. LeetCode 547: 朋友圈
2. LeetCode 684: 冗余连接
3. LeetCode 128: 最长连续序列
4. POJ 1611: The Suspects (并查集基础应用)
5. CodeForces 25D: Roads not only in Berland (并查集应用)

总结

并查集是一种简单高效的数据结构，特别适合处理元素分组和连通性问题。掌握好路径压缩和按秩合并这两个优化技巧，能够使并查集的操作效率接近常数级别，是竞赛中的必备工具。