Union Find with weighting and path compression


  • 1

    It is the classic application of Union Find. Same idea as Number of Island II.
    For those who is not familiar with Union Find see here for a good note. See also my blog here

    Java

    public class Solution {
    
        public int countComponents(int n, int[][] edges) {
            UnionFind sets = new UnionFind(n);
            for (int[] edge : edges) sets.unite(edge[0], edge[1]);
            return sets.size();
        }
    
    }
    
    class UnionFind {
        private int[] id;
        private int[] sz;
        private int count;
    
        public UnionFind(int n) {
            id = new int[n];
            sz = new int[n];
            for (int i = 0; i < n; ++i) {
                id[i] = i;
                sz[i] = 1;
            }
            count = n;
        }
    
        public int size() {
            return this.count;
        }
    
        public void unite(int i, int j) {
            i = root(i);
            j = root(j);
            if (i == j) return;
            if (sz[i] < sz[j]) { //weighted quick union
                id[i] = j;
                sz[j] += sz[i];
            } else {
                id[j] = i;
                sz[i] += sz[j];
            }
            --count;
        }
    
        private int root(int i) {
            for (; i != id[i]; i = id[i])
                id[i] = id[id[i]]; //path compression
            return i;
        }
    }
    // 45 / 45 test cases passed.
    // Status: Accepted
    // Runtime: 3 ms

Log in to reply
 

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