Easiest 2ms Java Solution


  • 88

    This is 1D version of Number of Islands II. For more explanations, check out this 2D Solution.

    1. n points = n islands = n trees = n roots.
    2. With each edge added, check which island is e[0] or e[1] belonging to.
    3. If e[0] and e[1] are in same islands, do nothing.
    4. Otherwise, union two islands, and reduce islands count by 1.
    5. Bonus: path compression can reduce time by 50%.

    Hope it helps!

    public int countComponents(int n, int[][] edges) {
        int[] roots = new int[n];
        for(int i = 0; i < n; i++) roots[i] = i; 
    
        for(int[] e : edges) {
            int root1 = find(roots, e[0]);
            int root2 = find(roots, e[1]);
            if(root1 != root2) {      
                roots[root1] = root2;  // union
                n--;
            }
        }
        return n;
    }
    
    public int find(int[] roots, int id) {
        while(roots[id] != id) {
            roots[id] = roots[roots[id]];  // optional: path compression
            id = roots[id];
        }
        return id;
    }
    

  • 1

    Path compression, not pass compression.


  • 0

    Haha. Thanks just updated Stefan.


  • 0
    Y

    what is the time complexity ? is it O(E*E) ?


  • 2

    The complexity for M quick union + path compression on N objects should be N + MlgN, I think in this problem, M = 2E, N = V, so O(V + 2ElgV), correct me if this is wrong @yavinci


  • 0
    B

    @Ximin.Z I am wondering if find() method is O(1) in this case?


  • 0

    a smart way of using union found when already know there will n points in total


  • 0
    D

    exactly the same idea! union find, a clever and fast processing data structure!


  • 1
    C

    Hi, @yavinci Thanks for sharing your code. For the path compression part, it is compressing the node for one level smaller, but not directly to its root, right? I think this is good enough, but just to check with you about intention behind that code snippet.


  • 1
    C

    @yavinci Just another improvement to your path compression union find algorithm, add weight to each root in the tree. When only use path compression, the time complexity is (N + MlogN), with weighted quick union path compression the time complexity will be (N + M)*lgN. M is the number is unions in the array, and N is the number of nodes.

    public int countComponents(int n, int[][] edges) {
            
            if (null == edges || 0 == edges.length) return n;
            
            // build root array
            int[] roots = new int[n];
            // build size array (add weight to the tree)
            int[] size = new int[n];
            for (int i = 0; i < n; i ++) roots[i] = i;
            Arrays.fill(size, 1);
            
            // for each edge, change its root to its parant
            for (int i = 0; i < edges.length; i ++) {
                // for the nodes in each edge, use path compression to let it pointed to its root 
                int root1 = find(roots, edges[i][0]);
                int root2 = find(roots, edges[i][1]);
                if (root1 != root2) {
                    if (size[root1] < size[root2]) {
                        roots[root1] = root2;
                        size[root1] += size[root2];
                    }
                    else {
                        roots[root2] = root1;
                        size[root2] = size[root1];
                    }
                    n --;
                }
            }
            
            return n;
        }
        
        private int find(int[] roots, int node) {
            
            while (roots[node] != node) {
                roots[node] = roots[roots[node]];
                node = roots[node];
            }
            return node;
        }
    

  • 0
    D

    @yavinci

    Could you explain what exactly the path compression does ?


  • 0
    D

    @dreamer92

    Here if we don't write roots[id] = roots[roots[id]] (which is path compression) then every time we call find for id, we are traversing parent tree till root, but by writing this line we are reducing path to parent. That means we have reduced path to reach parent of current id, Hence this is called path compression.

    If it's still not clear then take a sample graph and see how parent array is different with and without path compression.

    HTH.


Log in to reply
 

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