# Union Find with weighting and path compression

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

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