【并查集】Leetcode 547.省份数量_使用并查集 完成leetcode省份数量问题

Leetcode 547. 省份数量

题目描述：有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。

解题思路：使用并查集实现。并查集的两个主要的函数——查找find，和合并Union如下：

int find(int x) {
	if (x == father[x]) {
		return x;
	}
	return father[x] = find(father[x]);//压缩路径的写法
}

void Union(int a, int b) {
	int root_a = find(a);
	int root_b = find(b);
	if (root_a != root_b) {
		father[root_a] = root_b;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

关于路径压缩的解释，可以参看文章：并查集

本题的本质实际上是要寻找连通块的个数。遇到这种题需要一个变量count用来实时统计连通块个数。具体的实现可以是：第一步，初始化一个father数组，对每个点它的father为本身，相当于最开始为n个独立的点，即连通块个数为n；第二步，可以如果两个点相连，那就将两个点使用Union函数进行合并，调用一次Union，连通块个数就减一（count–）。

需要trip的点：

1. 程序中对于某个点（比如3），它和1相连，这时你会将father[3] = 1，然后它又和2相连，你又会需要father[3] = 2，这种情况下，大家可能会想，这丢失了3和1相连的信息了呀，但实际并不影响连通块count的计数的，因为3和1相连的时候，那连通块的个数确实此时少了1，所以count–，然后3和2相连，那此时也就3、2和1都连在一起了呀，count是不是应该再减一对吧，所以这里是没有问题的。
2. isConnect是主对角对称的，第二层循环时，只需要j<i时进行，也就是只处理矩阵右上角，避免重复相连。

class Solution {
private:
    vector<int> father;
    int count;
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        //1. 全局变量初始化
        int n = isConnected.size();
        count = n;//省份的个数
        for (int i = 0; i < n; ++i) {
            father.push_back(i);//初始化为n个独立的连通块
        }
        
        //[[1,1,0],
        // [1,1,0],
        // [0,0,1]]
        // isConnected关于主对角线对称
        //2. 相连的点进行合并，合并时更新count
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (isConnected[i][j]) {
                    Union(i, j);
                }
            }
        }

        return count;
    }

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

    void Union(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);
        if (root_a != root_b) {
            father[root_a] = root_b;
            count--;//更新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
32
33
34
35
36
37
38
39
40
41
42
43
44
45