【LeetCode】并查集深入浅出，一文吃透！

算法

发布日期: 2021-01-26

文章字数: 1.6k

阅读时长: 6 分

阅读次数:

【LeetCode】并查集

原文同步在：https://github.com/EricPengShuai/Interview/blob/main/algorithm/并查集.md

0. 概念

并查集主要用于解决一些 元素分组 问题，通过以下操作管理一系列不相交的集合：

合并（Union）：把两个不相交的集合合并成一个集合
查询（Find）：查询两个元素是否在同一个集合中

具体实现方面，使用一个数组 parent 存储每个变量的 父节点信息（每个节点的连通分量信息），其中的每个元素表示当前变量所在的连通分量的父节点信息，如果父节点是自身，说明该变量为所在连通分量的根节点。初始化时所有变量的父节点都是它们自身。

初始化：将每个节点的父节点指向自己。表示每个每个节点最开始都是自己一个集合，也就是节点的父节点都是自己
```
vector<int> parent(n);
iota(parent.begin(), parent.end(), 0);
```

查找时，沿着当前分量的父节点一路向上查找，直到找到根节点，这个过程也叫 路径压缩，具体来说有两种方法
- 隔代压缩：性能比较高，虽然压缩不完全，不过多次执行隔代压缩也能达到完全压缩的效果，这个方法也叫迭代查找
```
int find(int x) {
    while (x != parent[x]) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}
```
- 完全压缩：需要借助系统栈，使用递归的写法。或者先找到当前节点的根节点，然后把沿途上所有的节点都指向根节点，得遍历两次，这个方法也叫递归查找
```
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}
```

合并时，将属于同一类的节点合并到一个树中，设计 union(x, y) 将 x 的根节点指向 y 的根节点
```
// 最好不要申明为 union，这是一个关键字
void Union(int x, int y) {
    parent[find(x)] = find(y);
}
```
在合并时还可以 按秩合并，秩没有明确的定义，一般可以指以节点为根节点的子树的深度，也可以表示以根节点的子树的节点个数，考虑按秩合并之后可以让查找的效率更高
- 以秩比较大的节点为根合并：最大深度没有增加
- 以秩比较小的节点为根合并：最大深度有增加

1. 模板

1.1 维护深度——秩

class UnionFind
{
private:
    vector<int> parent;
    vecotr<int> rank;	// 维护以节点为根节点的子树的深度——秩
    
public:
    UnionFind(int size) {
        parent.resize(size);
        iota(parent.begin(), parent.end(), 0);
        
        rank = vector<int>(size, 1);
    }
    
    // 隔代压缩，迭代查找
    int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    
    // 按秩合并
    void Union(int x, int y) {
        int x_root = find(x), y_root = find(y);
        if (x_root == y_root) return;	// 如果已经处于一个集合了直接返回
        
        // 注意这里只要最大的深度不变就不需要修改根节点的秩
        if (rank[x_root] < rank[y_root]) { // 以深度大的节点为根
            parent[x_root] = y_root;
        } else if (rank[x_root] > rank[y_root]) {
            parent[y_root] = x_root;
        } else {	// 深度一样，谁作为根节点都可以
         	parent[y_root] = x_root;
            rank[x_root] ++;	// 作为根节点的高度会+1
        }
    }
}

1.2 维护连通分量个数

class UnionFind
{
    vector<int> parent;
    vector<int> size;	// 当前节点为根节点的子树节点总数
    int count;	// 连通分量个数
   
public:
    UnionFind(int n) {
        count = n;	// 初始是每个节点都是一个连通分量
        parent.resize(n), size.resize(n);
        iota(parent.begin(), parent.end(), 0);
        iota(size.begin(), size.end(), 0);
    }
    
    // 完全压缩，递归查找
    int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    // 按照连通分量个数合并
    void Union(int x, int y) {
        int x_root = find(x), y_root = find(y);
        if (x_root == y_root) return;	// 如果已经处于一个集合了直接返回
        
        if (size[x_root] > size[y_root]) {	// 节点少分量合并到节点多的分量上
            parent[y_root] = x_root;
            size[x_root] += size[y_root];
        } else {
            parent[x_root] = y_root;
            size[y_root] += size[x_root];
        }
        -- count; // 合并时候连通分量个数减1
    }
    
    int getSize(int x) {
        int root = find(x);
        return size[root];
    }
    
    int getCount() {
        return this->count;
    }
}

初始不知道节点个数的写法：维护哈希表

class UnionFind
{
public:
    unordered_map<int, int> parent;
    // 连通分量个数
    int count = 0;

    int find(int index) {
        if (parent.find(index) == parent.end()) {
            parent[index] = index;
            // 这里最初不知道节点个数需要在哈希表加入元素时候初始化
            count ++;  
        }

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

    void Union(int index1, int index2) {
        int parent1 = find(index1);
        int parent2 = find(index2);
        // *这步骤很重要，直接把两节点首领一样的结果返回过滤，否则会让count多减1*
        if (parent1 == parent2) {
            return;
        }
        parent[parent1] = parent2;
        count --;  // 也是合并时候连通分量减1
    }
};

2. 例题

基础

题目	说明	答案
990. 等式方程的可满足性	先将==全部合并，其次找出!=的根节点，如果一样则不行	通过
547. 省份数量	简单的并查集，维护连通分量个数，也可以 DFS 和 BFS	通过

进阶

题目	说明	答案
959. 由斜杠划分区域	重点在将斜杠怎样拆分成单元格，外部添加成33（还可以DFS），内部分解成44	通过 DFS
721. 账户合并	维护账户到id的哈希表，合并含有相同账户的id	通过
1584. 连接所有点的最小费用	Kruskal 算法：构造边，排序之后合并连通分量，维护分量长度和节点个数	通过
1697. 检查边长度限制的路径是否存在	离线查询（询问全部给出，但是没必要按照询问的顺序处理，可以排序之后离线处理），注意自定义 sort 排序时最好加上引用`&`	通过
2503. 矩阵查询可获得的最大分数	可以考虑`点权`或者`边权`（边权就考虑较大边），排序之后然后离线查询，询问排序下标就可以，可以看看灵神视频题解	边权点权