[数据结构与算法]547省份数量

547省份数量

深度优先搜索

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int provinces=isConnected.length;
        boolean[] visited=new boolean[provinces];
        Arrays.fill(visited,false);
        int circles=0;
        for (int i=0;i<provinces;i++){
            //i这个城市没有被访问过
            if (!visited[i]){
                visited[i]=true;
                dfs(isConnected,visited,i);
                circles++;
            }
        }
        return circles;

    }
    public void dfs(int[][] isConnected,boolean[] visited,int i){
        for (int j=0;j<visited.length;j++){
//            要确保i这个城市没有被访问过
            //j这个城市没有被访问过，而且i和j是连通的
            if (!visited[j] && isConnected[i][j]==1){
                visited[j]=true;
                dfs(isConnected,visited,j);
            }
        }
    }
}

时间复杂度$O(n^2)$，二维数组里的每一个元素都要遍历一次。
空间复杂度$O(n)$，辅助数组，递归栈不会超过$n$，只有$n$个城市。

广度优先搜索

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int provinces=isConnected.length;
        boolean[] visited=new boolean[provinces];
        Arrays.fill(visited,false);
        int circles=0;
        Queue<Integer> que=new LinkedList<>();
        for (int i=0;i<provinces;i++){
            //i这个城市没有被访问过
            if (!visited[i]){
                que.add(i);
                while (!que.isEmpty()){
                    Integer j = que.poll();
                    visited[j]=true;
                    for(int k=0;k<provinces;k++){
                        if (!visited[k] && isConnected[j][k]==1){
                            que.add(k);
                        }
                    }
                }
                circles++;
            }
            
        }
        return circles;
    }
}

时间复杂度$O(n^2)$。
空间复杂度$O(n)$。

并查集

class Solution {
   public int findCircleNum(int[][] isConnected) {
        int provinces = isConnected.length;
        int[] parent = new int[provinces];
        int circles=0;

        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的parent
                    union(parent,i,j);
                }
            }
        }
        for (int i = 0; i < provinces; i++) {
            if (parent[i]==i){
                circles++;
            }
        }
        return circles;
    }


    public void union(int[] parent,int a,int b){
        parent[find(parent,b)] = parent[find(parent,a)];

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

时间复杂度$O(n^2\log n)$。这里的并查集使用了路径压缩。
空间复杂度$O(n)$。