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

https://algs4.cs.princeton.edu/15uf/

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top