Better implementation to find the root of an element in QuickUnion implementation of UnionFind problem
-
05-11-2019 - |
Question
I wanted to know which implementation is better to find the root of the element in the Quick Union implementation of the UnionFind problem. The professor has used a while loop to find the root of the element, while I have implemented it using a recursive approach. Which approach is better in terms of space complexity, and scalability for large arrays?
//Quick union method for Union-find algorithm. Lazy approach
import java.util.Scanner;
public class QuickUnionUF {
private int [] id;
public QuickUnionUF(int N)
{
id= new int[N];
for(int i=0; i<id.length;++i)
{
id[i]=i;
}
}
public int root(int p)
{
if(id[p]==p) return p;
else return(root(id[p]));
}
public boolean isConnected(int p, int q)
{
return (root(p)==root(q));
}
public void union(int p, int q){
int proot= root(p);
int qroot= root(q);
id[proot]= qroot;
}
}
For the root function, the professor has used -
public int root(int p) {
while (p != id[p])
p = id[p];
return p;
}
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange