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

• 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;
}
}
``````

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