算法练习帖--61--省份数量(Java)_省份数量 深度优先 java

省份数量

一、题目描述

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

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

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

返回矩阵中 省份 的数量。
(题目来源：力扣（LeetCode）)

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

示例 2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
1
2
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

二、解决方法

1. 并查集

class Solution {
    class UnionFind{
        int count;//统计省份数
        int[] parent;//父结点数组
        int[] rank;//秩数组
		/**
		*	初始化方法
		**/
        public UnionFind(int size) {
            parent=new int[size];
            rank=new int[size];
            count=size;
            for (int i = 0; i < size; i++) {
                parent[i]=i;
            }
        }
		/**
		* 查找父类方法
		*/
        public int find(int index){
            while(index!=parent[index]){
                parent[index]=parent[parent[index]];
                index=parent[index];
            }
            return index;
        }
		/**
		* 合并集合方法
		*/
        public void union(int index1,int index2){
            int root1=find(index1);
            int root2=find(index2);
            if(root1==root2){return;}
            if(rank[root1]>rank[root2]){
                parent[root2]=root1;
            }else if(rank[root1]<rank[root2]){
                parent[root1]=root2;
            }else{
                parent[root2]=root1;
                rank[root1]+=1;
            }
            count--;
        }
    }
    public int findCircleNum(int[][] isConnected) {
    	//并查集对象
        UnionFind uf = new UnionFind(isConnected.length);
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = 0; j < isConnected[0].length; j++) {
                if(isConnected[i][j]==1){
                	//合并
                    uf.union(i,j);
                }
            }
        }
        return uf.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

2. 并查集（官方题解）

package com.lxf.test2;

class FindCircleNum {
    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) {
                    //合并
                    union(parent, i, j);
                }
            }
        }
        int circles = 0;//省份数
        for (int i = 0; i < provinces; i++) {
            //统计parent数组中有多少个集合，也就是省份数
            if (parent[i] == i) {
                circles++;
            }
        }
        return circles;
    }

    /**
     * 合并方法
     * @param parent 父结点数组
     * @param index1 合并结点1
     * @param index2 合并结点2
     */
    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

    /**
     * 查找父结点方法
     * @param parent 父结点数组
     * @param index  查找结点
     * @return
     */
    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
42
43
44
45
46
47
48
49
50

3.DFS(深度优先算法，官方题解)

class Solution {
    public int arrL;//数组长度
    public int findCircleNum(int[][] isConnected) {
        arrL=isConnected.length;
        boolean[] visited=new boolean[arrL];//记录是否访问过结点的数组
        int count=0;//省份数量
        for (int i = 0; i < arrL; i++) {
            if(!visited[i]){
            	//当前结点未访问过，省份+1
                count++;
                //将该结点所有连通结点访问一边
                dfs(isConnected,visited,i);
            }
        }
        return count;
    }

    private void dfs(int[][] isConnected,boolean[]  visited,int i) {
        for (int j = 0; j < arrL; j++) {
            if(isConnected[i][j]==1&&!visited[j]){
            	//将该节点的所有相连且未被访问过的结点全部访问，且将状态置为访问过
                visited[j]=true;
                //再将相连结点递归查找
                dfs(isConnected,visited,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

4.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
27
28
29
30
31