Clear Weighted Quick Union Solution - JAVA, O(nlgn)


  • 0

    This is the solution using Weighted Quick Union, the tree inside UF will keep balanced all the time.

    public class Solution {
        public int countComponents(int n, int[][] edges) {
            WeightedQuickUionFind uf = new WeightedQuickUionFind(n);
            for(int i = 0; i < edges.length; i++){
                int[] pair = edges[i];
                int p = pair[0], q = pair[1];
                uf.union(p, q);
            }
            return uf.count();
        }
    }
    
    class WeightedQuickUionFind{
        private int count;
        private int[] id;
        private int[] sz;
        
        public WeightedQuickUionFind(int size){
            this.count = size;
            this.id = new int[size];
            this.sz = new int[size];
            for(int i = 0; i < size; i++){
                id[i] = i;
                sz[i] = 1;
            }
        }
        
        public void union(int p, int q){
            int i = find(p), j = find(q);
            if(i == j)  return;
            if(sz[i] > sz[j]){ id[j] = i; sz[i] += sz[j]; }
            else             { id[i] = j; sz[j] += sz[i]; }
            count--;
        }
        
        public boolean connected(int p, int q){
            return find(p) == find(q);
        }
        
        public int find(int p){
            while(p != id[p])
                p = id[p];
            return p;
        }
        
        public int count(){
            return this.count;
        }
    }
    

Log in to reply
 

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