# Java solution, Union Find

• This is a typical `Union Find` problem. I abstracted it as a standalone class. Remember the template, you will be able to use it later.

``````public class Solution {
class UnionFind {
private int count = 0;
private int[] parent, rank;

public UnionFind(int n) {
count = n;
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}

public int find(int p) {
while (p != parent[p]) {
parent[p] = parent[parent[p]];    // path compression by halving
p = parent[p];
}
return p;
}

public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
if (rank[rootQ] > rank[rootP]) {
parent[rootP] = rootQ;
}
else {
parent[rootQ] = rootP;
if (rank[rootP] == rank[rootQ]) {
rank[rootP]++;
}
}
count--;
}

public int count() {
return count;
}
}

public int findCircleNum(int[][] M) {
int n = M.length;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (M[i][j] == 1) uf.union(i, j);
}
}
return uf.count();
}
}
``````

• ``````            if (rank[rootQ] > rank[rootP]) {
parent[rootP] = rootQ;
}
else {
parent[rootQ] = rootP;
if (rank[rootP] == rank[rootQ]) {
rank[rootP]++;
}
}

Could you explain this part ? @shawngao``````

• @dreamer92 That code snippet is used to decide which node will be used as `Parent` during `Union` two sets.

• This is a typical `Union Find` problem - a similar problem is Graph Valid Tree
A bit advanced Union Find problems are Number of Islands II and Number of Connected Components

``````    public int findCircleNum(int[][] M) {
int m = M.length, cnt = 0;
int[] root = new int[m];
for (int i = 0; i < m; i++) root[i] = i;
for (int i = 0; i < m; i++)
for (int j = i + 1; j < m; j++)
if (M[i][j] == 1) unionFind(root, i, j);

for (int i = 0; i < m; i++)
if (i == root[i]) cnt++;
return cnt;
}

void unionFind (int[] root, int v1, int v2) {
while (root[v1] != v1) v1 = root[v1]; //find v1's root
while (root[v2] != v2) v2 = root[v2]; //find v2's root
if (root[v1] != root[v2]) root[v2] = v1; //unite the 2 subtrees
}``````

• @zzhai

I do not think it is necessary to count the root nodes after the union-find operations, you just need minus 1 when you do a union operation.

``````  public int findCircleNum(int[][] M) {
int count = M.length, roots[] = IntStream.range(0, M.length).toArray();
for (int i = 0; i < M.length; i++)
for (int j = i + 1, rootI = getRoot(roots, i), rootJ; j < M.length; j++)
if (M[i][j] == 1 && rootI != (rootJ = getRoot(roots, j))) {
roots[rootJ] = rootI;
count--;
}
return count;
}

public int getRoot(int[] roots, int leaf) {
while (leaf != roots[leaf]) leaf = roots[leaf] = roots[roots[leaf]];
return leaf;
}``````

• Share my Union-Find solution which is a little more concise in the "Find" and "Union" part

``````public class Solution {
static int[] father;
public int findCircleNum(int[][] M) {
//corner case
if(M.length == 0 || M[0].length == 0) return 0;

int m = M.length;
father = new int[m];
for(int i = 0; i < m; i++){
father[i] = i;
}
int counter = m;//initial counter as m

for(int i = 0; i < m ; i++){
for(int j = i + 1; j < m; j++){
if(M[i][j] == 1){
//Only need to union when they are in different groups
int father1 = find(i);
int father2 = find(j);
if(father1 == father2) continue;

union(i, j);
counter--;
}
}
}

return counter;
}

private int find(int root){
if(father[root] == root) return father[root];

father[root] = find(father[root]);
return father[root];
}

private void union(int root1, int root2){
int father1 = find(root1);
int father2 = find(root2);

if(father1 != father2){
father[father1] = father2;
}
}
}
``````

• Sorry, what is the rank used for?

• @shawngao Could you please explain why "rank" is being used in your code?

• @kaddusingh Hi I think I found the answer from the book "Introduction to Algorithms" "CLRS". Basically this will provide a clue when you try to union 2 sets. 1 shorter 1 longer and bigger. So when you union, you would just want to update as few as possible. So we can keep a rank record to help us decide who is the smaller one and who is the bigger one to save us some time.

• in this solution, since he iterates the points in ascending order and j is always greater or equals to i.
It is not necessary to keep the rank.
We can always just do parent[rootP] = rootQ;

• I don't think you need a extra "rank" array here, only a parent array is enough right?

• @xinlin5 You can say that. Rank array is used to accelerate union operation. It's in the original template. http://algs4.cs.princeton.edu/15uf/UF.java.html

• Same idea. Just a little bit difference.

``````class Solution {
int[] father;
public class UnionFind {
public UnionFind(int n) {
for (int i = 1; i <= n; i++) {
father[i] = i;
}
}

public int find(int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father[x]);
}

public boolean query (int a, int b) {
int x = find(a);
int y = find(b);
return x == y;
}

public void union (int a, int b) {
int x = find(a);
int y = find(b);
if(x != y) {
father[x] = y;
}
}
}

public int findCircleNum(int[][] M) {
int n = M.length;
father = new int[n + 1];
UnionFind uf  = new UnionFind(n);
int count = n;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if(M[i][j] == 1 && !uf.query(i, j)) {
count--;
uf.union(i,j);
}
}
}
return count;
}
}
``````

• We don't need to call the find method every time for both row and column indexes (i and j). Instead, we only need to call the find method only once for row index (i) before the going to the loop of column index (j). But in this way, we need to update the find result of i every time after the union. To do this, we can let the union method to return the final root to update the i value.
I also write the union find to weighted and path compression union find. The time complexity is `O(n^2*logn)`.

``````    public int findCircleNum(int[][] M) {
int m = M.length;
if(m==0) return 0;

int[] roots = new int[m];
int[] sc = new int[m];
for(int i=0;i<m;i++) roots[i]=i;
Arrays.fill(sc,1);

int count=m;
for(int i=0;i<m;i++)
{
int x= find(roots,i);
for(int j=i+1;j<m;j++)
{
if(M[i][j]!=1) continue;
int y= find(roots,j);
if(x!=y)
{
count--;
x=union(roots,x,y,sc);
}
}
}
return count;
}

public int find(int[] roots, int i) {
while(roots[i]!=i)
{
roots[i]=roots[roots[i]];//path compression
i=roots[i];
}
return i;
}

public int union(int[] roots, int x, int y, int[] sc) {
if(sc[x]>sc[y])//weighted union
{
roots[y]=x;
sc[x]+=sc[y];
return x;
}
else
{
roots[x]=y;
sc[y]+=sc[x];
return y;
}
}
``````

• The rank can be stored at root node using negative number, so if node value is negative, it's root and the number represents rank of this UF tree.

• ``````rank is good!  However you need to update the tree's height when you finished a find operation: since this operation might short the tree's height

for example :          a
/\
b  d
/
c

After you did a find(c)
the tree become
a
/|\
b c d
``````

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