Leetcode.547. 省份数量---DFS/并查集_leetcode省会城市

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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

题解：

方法一：DFS（深度优先搜索）

• 我们直接任选一个城市开始搜索，将与此城市有连通的所有城市全部搜索完毕，并将所有搜索过的城市进行标记。接着我们继续下一个城市进行搜索即可，如此循环往复我们即可搜索完毕所有城市，且每次成功深搜一次我们就让省份数量加一即可。

class Solution {

    public int findCircleNum(int[][] isConnected) {
        boolean[] flag = new boolean[isConnected.length];
        int res = 0;
        for(int i=0;i<isConnected.length;i++){
            if(!flag[i]){
                dfs(flag,isConnected,i);
                res++;
            }
        }

        return res;
    }

    public void dfs(boolean[] flag,int[][] isConnected,int i){
        for(int j=0;j<isConnected.length;j++){
            if(isConnected[i][j]==1 && !flag[j]){
                flag[j] = true;
                dfs(flag,isConnected,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

方法二：并查集

我们可以先通过一个大神的博客并查集入门来简单了解一下基本的并查集用法及其含义。

• 本题显然是一个基本并查集的问题，我们先让所有的城市作为互不连接的独立省份存在，接着根据题目所给的isConnected数组来判断对哪些互不连接的省份之间进行连接，为了完成连接操作，我们使用并查集里的union函数进行连接。
• 在对所有的城市进行相应连接以后，即初始化了我们定义的并查集后，对这个并查集进行查找，查找此并查集共分为几个部分，接着对这些部分求和即为所形成的省份数量。

class Solution {

    public int findCircleNum(int[][] isConnected) {
        int res = 0;
        int[] par = new int[isConnected.length];
        for(int i=0;i<isConnected.length;i++){
            par[i] = i;
        } 

        for(int i=0;i<isConnected.length;i++){
            for(int j=0;j<isConnected[0].length;j++){
                if(isConnected[i][j]==1){
                    union(i,j,par);
                }
            }
        }

        for(int i=0;i<isConnected.length;i++){
            if(par[i]==i){
                res++;
            }
        }

        return res;
    }

    public void union(int x,int y,int[] par){
        int tx = find(x,par);
        int ty = find(y,par);
        if(tx!=ty){
            par[tx] = ty;
        }
    }

    public int find(int x,int[] par){ 
        while(par[x]!=x){
            x = par[x];
        }

        return x;
    }
}
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