LeetCode 省份数量

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

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

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

返回矩阵中 省份 的数量。

提示：

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.com/problems/number-of-provinces

利用深度优先搜索
对应的代码：

class Solution {
/*
如果定义一个二维数组的话，那么下面判断城市是否已经是否已经被访问过了应该是
visited[i][i]是否等于true，如果是，则表示i城市已经被访问过了，否则没有。
但是这样的话就会导致空间浪费，因为之利用了n个数，所以为了避免空间的浪费，
将visited定义成为了一个一维数组
*/
    boolean[] visited;
    public int findCircleNum(int[][] isConnected) {
        if(isConnected == null || isConnected.length == 0 || isConnected[0].length == 0)
          return 0;
        int result = 0,i,j,col = isConnected.length;
        visited = new boolean[col]; //标记这个城市是否已经被访问过了
        for(i = 0; i < col; i++){
               if(visited[i] == false){
               /*
               判断下标为i的城市是否已经被访问过了，如果没有被访问过，那么
               就进入深度优先搜索，从而将找到和这个城市在同一个省份的城市
               （即相连或者间接相连的）。
               注意数组是n * n的二维数组，此时就有n个城市，即行下标和列下
               标相等的才是对应的城市.所以如果定义的是个二维数组visited
               来标记是否已经被访问过时，判断条件应该是visited[i][i]，
               但是这样的话就会导致空间的浪费，所以visited定义成为了一个
               一维数组，当visited[i]为true的时候表示i这个城市已经被访问
               过了,否则没有被访问过
               */
                   dfs(isConnected,i,col); //由于是n * n数组，所以是col = row
                   result++;
               } 
        }
        return result;
    }
    public void dfs(int[][] isConnected,int index,int row){
        visited[index] = true;
        //深度优先遍历和x、y相邻的顶点
        int j;
        for(j = 0; j < row; j++){
        /*
        如果index这个城市和j城市相连，并且j城市没有被访问过，那么就进入深
        度优先搜索
        */
            if(isConnected[index][j] != 0 && visited[j] == false)
              dfs(isConnected,j,row);
        }
    }
}
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

运行结果：