三题带你了解并查集，记得要看最后的总结哦~

一、引入 · 省份的数量

https://leetcode-cn.com/problems/number-of-provinces/

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

这是一题并查集入门题，我们主要通过此题来了解并查集用于解决怎样的问题。

我们可以利用集合的思想，将相连的城市并入一个集合（题意中的省），则求省份的数量就是求合并完成后集合的数量。

因此，我们可以理解为，并查集可以作为一个少数据量下分类和聚类的一个工具。

二、定义

​ 并查集的取名来源于“并”（Union）、“查”（Find）、“集”（Set），因此并查集主要解决两个问题：

  • 合并：将两个集合合并
  • 查找：判断两个元素是否在同一个集合中

为了节省开销，并查集一般用树来表示集合，一棵树代表一个集合。数据结构上使用一维数组，利用树顺序存储时父子节点的下标关系 x = y / 2 来实现快速遍历。

一般设计 father[index] 数组，下标 index 表示元素的下标，father[index] 是下标为 index 的父节点的下标。

【注意】：树的顺序存储下标从 1 开始。

初始化

一开始，每一个元素都是一个独立的集合，则每一个数的父节点都是其本身。

1
2
3
for (int i = 1; i <= N; i++) {
    father[i] = i;
}

查找

查找操作就是对给定节点通过父子关系，不断向上查找父节点，直至根节点。如果两个给定节点具有相同的根节点，则两节点隶属于同一集合。

1
2
3
4
5
int findFather (int x) {
    while (x != father[x]) {  // 如果不是根节点，则需不断向上查找
        x = father[x];
    }
}

亦可以使用递归的写法：

1
2
3
4
int findFather (int x) {
    if (x == father[x]) return x;
    else return findFather(father[x]);  // 如果不是根节点，则需不断向上查找
}

合并

合并就是把两个集合合并为一个集合。合并的步骤分为两步：

  1. 判断给定的两元素是否属于同一集合（操作同 查找）
  2. 如不属于同一集合则合并：将两元素的根元素 faA 和 faB 相连（即 father[faA] = faB 或 father[faB] = faA）

用代码表述：

1
2
3
4
5
6
7
void Union(int a, int b) {
    int faA = findFather(a);  // 查找a的根节点
    int faB = findFather(b);  // 查找b的根节点
    if (faA != faB) {   // 如果两元素不属于同一集合（根节点不同），则合并
        father[faA] = faB;
    }
}

三、路径压缩与按秩合并

路径压缩

​ 第二章所述的并查集存储结构是没有经过优化的，一般如下图左侧所示。单链状的结构会增加查询的次数；优化的目的是为了减少查询次数（即树的高度），所以我们可以将单链转化为 N 叉树，如下右图所示。

image-20210217165052335 
1
2
3
4
5
6
7
8
9
10
int findFather(int x) {
    int a = x;
    while (x != father[x]) x = father[x]; // 不断寻找根节点，最后根节点为x
    while (a != father[a]) {  // 将每一个普通节点指向根节点
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}

路径压缩后的查找操作复杂度可视为 O(1) 。

按秩合并

因为层数越多，搜索代价越大，因此按秩合并的目的就在于减少层数。因此我们若将层数低的树作为父节点，则相比层数高度作为父节点，合并后的层数可能较少。如下图所示。

image-20210217171313257

用代码表述：

1
2
3
4
5
6
7
8
9
void Union(int a, int b) {
    int faA = findFather(a);  // 查找a的根节点
    int faB = findFather(b);  // 查找b的根节点
    if (rank[faA] > rank[faB]) father[faB] = faA;  // 小秩为父节点
    else {
        if (rank[faA] == rank[faB]) rank[faB]++;
        pre[faA] = faB;
    }
}

四、再次回到第一题

https://leetcode-cn.com/problems/number-of-provinces/

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

在 引入 章节我们已经对题意进行了简单分析：将相连的城市并入一个集合（题意中的省），求合并完成后集合的数量（题意中省份的数量）。

以下为代码表示（find 函数与 union 函数省略）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int findCircleNum(vector<vector<int>>& isConnected) {
    int provinces = isConnected.size();
    vector<int> parent(provinces);    // 创建father关系数组
    // 初始化
    for (int i = 0; i < provinces; i++) parent[i] = i;
    // 遍历给出的连通关系矩阵
    for (int i = 0; i < provinces; i++) {
        for (int j = i + 1; j < provinces; j++) {
            if (isConnected[i][j] == 1) {  // 对每两个连通的节点做合并操作
                Union(parent, i, j);
            }
        }
    }
    int circles = 0;
    for (int i = 0; i < provinces; i++) {
        if (parent[i] == i) {  // 输出每一个根节点（即集合的个数）
            circles++;
        }
    }
    return circles;
}

五、第二个例子 · 岛屿的数量

https://leetcode-cn.com/problems/number-of-islands/

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

​ 用并查集的思想可以很快整理出思路：最开始将每一个 1 视为一个岛屿，如果两个 1 相邻则并入一个集合，最后剩余集合的数量就是岛屿的数量。

​ 需要强调的是，我们在上一题（一维）的时候构建了一维的 father 数组，此题为了让读者可以更加简单地理解还是采用了一维的 father 数组，father[index] 的值表示：顺序存储时下标为 Index 的元素的父节点在顺序存储时的下标。

​ 首先写出 Find 和 Union 函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Find(vector<int> &father, int i, int j, int colNum) { // i和j为元素在二维数组中的下标
    if (father[i * colNum + j] != i * colNum + j) {   // 不断递归找到根节点
        int rowNo = father[i * colNum + j] / colNum;
        int colNo = father[i * colNum + j] % colNum;
        father[i * colNum + j] = Find(father, rowNo, colNo, colNum);
    }
    return father[i * colNum + j]; // 返回根节点
}

void Union(vector<int> &father, int i, int j, int i1, int j1, int colNum) {
    int result1 = Find(father, i1, j1, colNum);  // 找到传入的（相邻元素）的根节点
    int result2 = Find(father, i, j, colNum);  // 找到当前元素的根节点
    if (result1 != result2) {
        father[result1] = result2; // 建立两个根节点的父子关系
    }
}

对于外层函数，我们有三个步骤：

第一：构造 father 数组并初始化

1
2
3
4
5
6
vector<int> father(rowNum * colNum);
for (int i = 0; i < rowNum; i++) {
    for (int j = 0; j < colNum; j++) {
        father[i * colNum + j] = i * colNum + j;  // 最开始将每个元素的父元素设置为其本身
    }
}

第二：遍历二维向量以及合并（自然只有当前元素是“陆地”节点才有合并一说）

1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < rowNum; i++) {
    for (int j = 0; j < colNum; j++) {
        if (grid[i][j] == '1') { 
            // 检查上下左右的节点是否也是陆地（陆地是否相连），同时需要注意验证上下左右节点是否越界
            if (i + 1 < rowNum && grid[i + 1][j] == '1') Union(father, i, j, i + 1, j, colNum);
            if (i - 1 >= 0 && grid[i - 1][j] == '1') Union(father, i, j, i - 1, j, colNum);
            if (j + 1 < colNum && grid[i][j + 1] == '1') Union(father, i, j, i, j + 1, colNum);
            if (j - 1 >= 0 && grid[i][j - 1] == '1') Union(father, i, j, i, j - 1, colNum);
        }
    }
}

第三：遍历 father 数组，对根节点计数（岛屿数量）

1
2
3
4
5
6
7
int count = 0;
for (int i = 0; i < rowNum; i++) {
    for (int j = 0; j < colNum; j++) {
        // 岛屿需要满足两个条件：第一当前节点是陆地节点；第二当前节点是根节点
        if (Find(father, i, j, colNum) == i * colNum + j && grid[i][j] == '1') count++;
    }
}

最后将外层函数整合：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int numIslands(vector<vector<char>>& grid) {
    int rowNum = grid.size();
    int colNum = grid[0].size();
    // 构造father[]数组（结构为grid[][]的顺序存储）并初始化
    vector<int> father(rowNum * colNum);
    for (int i = 0; i < rowNum; i++) {
        for (int j = 0; j < colNum; j++) {
            father[i * colNum + j] = i * colNum + j;
        }
    }
    // 遍历矩阵，合并相连的节点
    for (int i = 0; i < rowNum; i++) {
        for (int j = 0; j < colNum; j++) {
            if (grid[i][j] == '1') {
                if (i + 1 < rowNum && grid[i + 1][j] == '1') Union(father, i, j, i + 1, j, colNum);
                if (i - 1 >= 0 && grid[i - 1][j] == '1') Union(father, i, j, i - 1, j, colNum);
                if (j + 1 < colNum && grid[i][j + 1] == '1') Union(father, i, j, i, j + 1, colNum);
                if (j - 1 >= 0 && grid[i][j - 1] == '1') Union(father, i, j, i, j - 1, colNum);
            }
        }
    }
    print(father);
    // 遍历，输出集合数量
    int count = 0;
    for (int i = 0; i < rowNum; i++) {
        for (int j = 0; j < colNum; j++) {
            if (Find(father, i, j, colNum) == i * colNum + j && grid[i][j] == '1') count++;
        }
    }
    return count;
}

六、最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

【这一题如果没有列入并查集专题，你能想到并查集吗？】

可以肯定是可以通过排序的方法来做。过程简单，此处不多说。我们主要介绍并查集的做法：

我们可以将所有连续的数纳入同一个集合（具体操作是：对于当前数，在给定的数组中寻找比当前数大 1 的数。如果存在则合并。），再用一个变量记录最大集合的元素数并及时更新。

首先我们写出 Find 和 Union 函数：（较第五章的例子更为简单，因此不做解释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Find(vector<int> &father, int index) {
    if (father[index] != index) Find(father, father[index]);
    return index;
}

void Union(vector<int> &father, vector<int> &count, 
           int index1, int index2) {
    int result1 = Find(father, index1);
    int result2 = Find(father, index2);
    if (result1 != result2) {
        father[result2] = result1;
        int num1 = count[result1];
        int num2 = count[result2];
        count[result1] = num1 + num2;
        count[result2] = num1 + num2;
    }
}

然后写出外层函数：

第一步：定义 father[] 数组 和 count[] 数组 并初始化（count 数组用于记录集合内的元素数量）

1
2
3
4
5
6
vector<int> father(size);
vector<int> count(size);
for (int i = 0; i < size; i++) {
    father[i] = i;
    count[i] = 1;
}

第二步：遍历数组，如果存在比当前数大 1 的，就合并

1
2
3
4
5
6
for (int i = 0; i < size; i++) {
    for (int j = 0; j< size; j++) {
        // 如果数组中存在着比当前数大1的，就合并
        if (nums[j] == nums[i] + 1) Union(father, count, i, j);
    }
}

第三步：再次遍历数组，选出 count 值最大的根节点（即拥有最多元素的集合）

1
2
3
4
int countMax = 1;
for (int i = 0; i < size; i++) {
    if (Find(father, i) == i) countMax = (count[i] > countMax ? count[i] : countMax);
}

【似乎是一题水题啊，可真的是这样吗？】

先不说在外层函数的第二步中，寻找比当前数大 1 的数的时间代价有多大。请各位读者思考：如果数组中出现重复数字上述算法还能否给出正确答案？

显然我们合并的是某一个值为 value 的节点 和 某一个值为 value+1 的节点，但是如果存在多个值为 value 和 值为 value + 1 的节点，我们需要将他们全部合并。此时，我们的代码就出现了问题。

似乎这是一个棘手的问题，但是，使用哈希表可以轻松解决并一举多得：

  • 使用哈希表可以将查找值为 value+1 节点的操作变成 O(1) 操作
  • 使用哈希表可以消除重复数字带来的困扰

具体实现和用普通向量的实现大同小异，只需多一步将给定的数组插入哈希表即可，此处不在给出重复的代码。

七、总结

在了解并查集思想以后我们会发现并查集的思想并不难，对于一些可以明显看出并查集思想的题目几乎可以认定为水题；但是，我们通过第六章可以知道有些题披着外衣但也可以用并查集的思想解决。【需要练习来加强敏感度】

当然本专题的例题并未使用按秩合并和路径压缩进行优化，因为在【第三章】中已详细讲解，作者不希望提供给读者过长的示例代码。

在本专题末尾希望提醒读者注意：

  1. 可以更多地考虑使用哈希表来代替普通数组，有时会有意想不到的惊喜【见第六章】
  2. 在一些较为复杂的题目背景下，希望读者可以仔细地推理，减少逻辑出错【见第五章】