AC JAVA code, Union Find


  • 23
    J
        private int[] father;
    public int countComponents(int n, int[][] edges) {
        
        Set<Integer> set = new HashSet<Integer>();
        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        for (int i = 0; i < edges.length; i++) {
             union(edges[i][0], edges[i][1]);
        }
        
        for (int i = 0; i < n; i++){ 
            set.add(find(i));
        }
        return set.size();
    }
    
    int find(int node) {
        if (father[node] == node) {
            return node;
        }
        father[node] = find(father[node]);
        return father[node];
    }
    
    void union(int node1, int node2) {
        father[find(node1)] = find(node2);
    }

  • 0
    S

    How can we determine the complexity of this solution?


  • 0
    Y

    you can find detailed explanation here :
    https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf


  • 0

    No need to use a hashset, every time you use the union function, the number of disjoint components will minus 1.


  • 0
    E

    @禽兽样 Not necessarily so. For example, if the components were somehow already connected (components where cycles exist), decreasing the number of components might leave you with 0 components or a negative count.


  • 0
    H

    I'm not sure. In order to have O(logn) find complexity, doesn't disjoint-set need to keep a depth[] array as well? Always do father[find(node1)] = find(node2) can result in O(n) find complexity.


  • 0

    @epishebe

    well actually you can use find to help, to define if the two nodes you are connecting have the same father or not
    so no need for hashset then


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.