Leetcode 547、省份数量

Leetcode 547、省份数量

方法一、DFS

遍历isConnected数组，如果当前位置是1且当前的i没有被访问过，调用dfs；每一次dfs都会把相连的地方进行标记，即：visited[i] = true，所以dfs执行的次数就是省份的数量。

class Solution {
    boolean[] visited;
    int len;
    public int findCircleNum(int[][] isConnected) {
        len = isConnected.length;
        visited = new boolean[len];
        int result = 0;

        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                if(!visited[i] && isConnected[i][j] == 1) {
                    dfs(i, isConnected);
                    result++;
                }
            }
        }

        return result;
    }

    public void dfs(int index, int[][] isConnected) {
        visited[index] = true;
        for(int i = 0; i < len; i++) {
            if(i != index && isConnected[index][i] == 1 && !visited[i]) {
                dfs(i, isConnected);
            }
        }
    }
}
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

方法二、BFS

思路和DFS相同，执行了几次BFS，就有几个省份。

    public int findCircleNum(int[][] isConnected) {
    
        int len = isConnected.length;
        boolean[] visited = new boolean[len];
        Queue<Integer> queue = new LinkedList<>();
        int result = 0;

        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                if(isConnected[i][j] == 1 && !visited[i]) {
                    queue.offer(i);
                    while(!queue.isEmpty()) {
                        int curr = queue.poll();
                        visited[curr] = true;
                        for(int k = 0; k < len; k++) {
                            if(isConnected[curr][k] == 1 && !visited[k]) {
                                queue.offer(k);
                            }
                        }
                    }
                    result++;
                }
            }
        }

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

方法三、并查集

每个省份属于一个集合，遍历isConnected数组对所有相连的地方进行合并，最后返回集合的个数。

    public int findCircleNum(int[][] isConnected) {
        int len = isConnected.length;
        UnionFindSet unionFindSet = new UnionFindSet(len);

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

        return unionFindSet.getCount();
    }

    class UnionFindSet{
        int[] parent;

        public UnionFindSet(int num) {
            parent = new int[num];

            for(int i = 0; i < num; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if(parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        public void union(int x, int y) {
            int px = find(x);
            int py = find(y);
            if(px != py) {
                if(parent[px] >= parent[py]) {
                    parent[py] = px;
                }else{
                    parent[px] = py;
                }
            }
        }
		
        public int getCount() {
            int result = 0;
            for(int i = 0; i < parent.length; i++) {
                if(parent[i] == i) result++;
            }
            return result;
        }
    }
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