LeetCode 547. 省份数量_547. 省份数量 java

547. 省份数量
     有 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]

注意：直接间接相连的算一个省份，其余没有关系的单独算一个省份

并查集：
是以根节点来相连。

// 直接间接相连的算一个省份，其余没有关系的单独算一个省份
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int provinces = isConnected.length;
        int[] parent = new int[provinces];
        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) {
                    //i和j有联系，要将他们联系起来
                    union(parent, i, j);
                }
            }
        }
        int circles = 0;
        for (int i = 0; i < provinces; i++) {
            if (parent[i] == i) {
            //根节点是自己才是单独的
                circles++;
            }
        }
        return circles;
    }

    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

public int find(int[] parent, int index) {
    if (parent[index] != index) {
        //寻找根节点
        parent[index] = find(parent, parent[index]);
    }
    return parent[index];
}

}


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

以输入[[1,1,1,1],[1,1,0,0],[1,0,1,0],[1,0,0,1]]，为例子。

第一次i=0,j=1时候： union(parent, i, j)后的结果为：parent[0]=1；
parent[0]的根节点为1.

第二次i=1,j=2时候：union(parent, i, j)后的结果为：parent[1]=2；
parent[1]的根节点为2.
注：此时的 parent[find(parent, index1)] 会进入find方法，此时的index1为0.

public int find(int[] parent, int index) {
        if (parent[index] != index) {
            //寻找根节点
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }
1
2
3
4
5
6
7

parent[0]=1, 所以parent[0] != 0,要寻找parent[0]的根节点，进入if语句进行寻找，找到其根节点为 1，再用返回的根节点的值

 public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }
1
2
3

所以最终find(parent, index1) =1；(因为是找到了0的根节点），而find(parent, index2)=2，所以此时 parent[find(parent, index1)] = find(parent, index2); 即为 parent[1] = 2；

第三次i=2,j=3时候：union(parent, i, j)后的结果为：parent[2]=3；
parent[2]的根节点为3.
注意：内部操作与第二次类似。都是以根节点来相连的。

第四次i=3,j=4时候：j超出范围，不执行union(parent, i, j)；

最终：当i=1，2，3时，j=i+1都没有满足isConnected[i][j] == 1这个条件，所以不再讨论。所以最后就
parent[0] =1,parent[1]=2,parent[2]=3,parent[3]=3,所以circles=1，答案为1.

二：BFS：深度优先搜索
深度优先搜索的思路是很直观的。遍历所有城市，对于每个城市，如果该城市尚未被访问过，则从该城市开始深度优先搜索，通过矩阵 isConnected 得到与该城市直接相连的城市有哪些，这些城市和该城市属于同一个连通分量，然后对这些城市继续深度优先搜索，直到同一个连通分量的所有城市都被访问到，即可得到一个省份。遍历完全部城市以后，即可得到连通分量的总数，即省份的总数。

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int provinces = isConnected.length;
        boolean[] visited = new boolean[provinces];
        int circles = 0;
        for (int i = 0; i < provinces; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, provinces, i);
                circles++;
            }
        }
        return circles;
    }

    public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {
        for (int j = 0; j < provinces; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                
                //深度优先，继续查看当前j城市与哪些城市相连
                dfs(isConnected, visited, provinces, 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

理解注意：
以输入[[1,1,1,1],[1,1,0,0],[1,0,1,0],[1,0,0,1]]，为例子。
在i=0时，进入第一次dfs，

public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {
        for (int j = 0; j < provinces; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                
                //深度优先，继续查看当前j城市与哪些城市相连
                dfs(isConnected, visited, provinces, j);
            }
        }
1
2
3
4
5
6
7
8
9

在此处会依次 visited[1]， visited[2]， visited[3]赋值为true.
在i=0的深度循环结束后，进行circles++操作。当i=1，i=2,i=3时都不满足 if (!visited[i])的条件，因为在第一次i=0的深度循环遍历的时候就都赋值为true了。

三：BFS广度优先搜索
也可以通过广度优先搜索的方法得到省份的总数。对于每个城市，如果该城市尚未被访问过，则从该城市开始广度优先搜索，直到同一个连通分量中的所有城市都被访问到，即可得到一个省份。

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int provinces = isConnected.length;
        boolean[] visited = new boolean[provinces];
        int circles = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < provinces; i++) {
            if (!visited[i]) {
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    visited[j] = true;
                    for (int k = 0; k < provinces; k++) {
                        if (isConnected[j][k] == 1 && !visited[k]) {
                            queue.offer(k);
                        }
                    }
                }
                circles++;
            }
        }
        return circles;
    }
}


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