LeetCode_并查集_DFS_BFS_中等_547.省份数量

1.题目

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

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

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

返回矩阵中省份的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-provinces

2.思路

（1）并查集
分析本题后发现可以直接使用并查集算法，有关并查集算法的模板可以参考核心框架汇总中的并查集算法，此处就不再赘述。

（2）深度优先搜索 (DFS)
本题也可以用 DFS 来解决。对于每个城市，如果该城市尚未被遍历过，则从该城市开始进行 DFS，直到该城市所处的连通分量中的所有城市都被遍历到，即可得到一个省份，并用变量 provinces 保存省份的数量（其初始值为 0）。此外，为了在遍历过程防止对城市进行重复遍历，可以用数组 visited 来记录每个城市节点是否被遍历。

（3）广度优先搜索 (BFS)
本题也可以用 BFS 来解决。对于每个城市，如果该城市尚未被遍历过，则从该城市开始进行 BFS，直到该城市所处的连通分量中的所有城市都被遍历到，即可得到一个省份，并用变量 provinces 保存省份的数量（其初始值为 0）。此外，为了在遍历过程防止对城市进行重复遍历，可以用数组 visited 来记录每个城市节点是否被遍历。

3.代码实现（Java）

//思路1————并查集
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int res = 0;
        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        //遍历邻接矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                	//如果第 i 个城市和第 j 个城市直接相连，那么将其连通
                    uf.union(i, j);
                }
            }
        }
        //连通分量(树)的个数即为本题中省份的数量
        return uf.getCount();
    }
}

//并查集
class UnionFind {
    //记录连通分量(树)的个数
    private int count;
    //节点 x 的父节点是 parent[x]
    private int[] parent;
    
    //构造函数
    public UnionFind(int n) {
        //初始时每个节点都是一个连通分量
        this.count = n;
        parent = new int[n];
        //初始时每个节点的父节点都是其自己，即每棵树中只有一个节点
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    //将 p 和 q 连通
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP != rootQ) {
            parent[rootQ] = rootP;
            // 两个连通分量合并成一个连通分量
            count--;
        }
        //如果 p 和 q 的父节点相同，它们本就是连通的，直接返回即可
    }
    
    //判断 p 和 q 是否互相连通，即判断 p 和 q 是否在同一颗树中
    public boolean isConnected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        //如果 p 和 q 的父节点相同，则说明它们在同一颗树中，即它们是连通的
        return rootP == rootQ;
    }
    
    //查找节点 x 的父节点，同时进行路径压缩，并且在路径压缩时维护数组 parent
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    //返回连通分量(树)的个数
    public int getCount() {
        return 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

//思路2————深度优先搜索 (DFS)
class Solution {
    public int findCircleNum(int[][] isConnected) {
        // n 表示城市数量
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, n, i);
                //城市 i 所处的连通分量中的所有城市都被访问到，此时即可得到一个省份
                provinces++;
            }
        }
        return provinces;
    }
    
    // DFS
    public void dfs(int[][] isConnected, boolean[] visited, int n, int i) {
    	visited[i] = true;
        for (int j = 0; j < n; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(isConnected, visited, n, j);
            }
        }
    }
}
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

//思路3————广度优先搜索 (BFS)
class Solution {
    public int findCircleNum(int[][] isConnected) {
        // n 表示城市数量
        int n = isConnected.length;
        //定义 visited 数组，防止对节点进行重复遍历
        boolean[] visited = new boolean[n];
        //省份数量，初始化为 0
        int provinces = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                //城市 i 未被访问过，从其开始 BFS
                queue.offer(i);
                visited[i] = true;
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    visited[j] = true;
                    //将与城市 j 相连的城市加入到 queue 中
                    for (int k = 0; k < n; k++) {
                        if (isConnected[j][k] == 1 && !visited[k]) {
                            queue.offer(k);
                        }
                    }
                }
                //城市 i 所处的连通分量中的所有城市都被访问到，此时即可得到一个省份
                provinces++;
            }
        }
        return provinces;
    }
}
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