Number of Operations to Make Network Connected 之 并查集

class Solution {
    Map> graph = new HashMap();
    boolean[] visited;
    public int makeConnected(int n, int[][] connections) {
        if(connections.length return -1;
        for(int[] edge: connections){
            graph.putIfAbsent(edge[0], new ArrayList());
            graph.putIfAbsent(edge[1], new ArrayList());
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        // true代表已经访问过，false代表未访问
        visited = new boolean[n];
        int count = 0;
        for(int i = 0; i ){
            if(!visited[i]&& dfs(i))
                count++;
        }
        return count-1;
    }
    public boolean dfs(int cur){
        if(visited[cur]) return true;
        if(!graph.containsKey(cur)) return true;
        visited[cur] = true;
        for(int next: graph.get(cur)){
            if(!visited[next])
                dfs(next);
        }
        return true;
    }
}

class Solution {
    public int makeConnected(int n, int[][] connections) {
        int[] parent = new int[n];
        for(int i = 0; i ){
            parent[i] = i;
        }
        int extraEdge = 0;
        int count = 0;
        for(int[] edge:connections){
            int p = findParent(parent, edge[0]);
            int q = findParent(parent, edge[1]);
            if(p == q) extraEdge++; //有公共祖先，说明此条边多余，可以去掉
            else parent[q] = p; //如果没有，根据connections矩阵，将两个点连接起来
        }
        for(int i = 0; i ){
            if(parent[i] == i) count++; //计算有多少个祖先，即多少个 单独的联通量
        }
        return (extraEdge >= count-1) ? count-1 : -1;
    }
    public int findParent(int[] parent, int x){
        while(parent[x] != x){
            x = parent[x];
        }
        return x;
    }
}