What is the difference between these 2 implementations of quick find?

134 Views Asked by At

I was learning about quick find and made a very basic implementation in java but my union function was not working properly when I initially implemented it. I made some changes and it started working but I'm not sure whats causing the problem in the first iteration of my function. I can see that for some reason the parent of P is changing even though I'm not making any changes to the argument p but I don't know why. Sorry if this is a stupid question I'm just lost here.

First attempt

public class QuickFindUF {

    private int[] id;

    public QuickFindUF(int N){
        id = new int[N];
        for (int i = 0;i<N;i++){
            id[i] = i;
        }
    }

    public boolean connected(int p, int q){
        if (id[p] == id[q]){
            return true;
        }
        return false;
    }

    public int find(int x){
        return id[x];
    }

    public void union(int p, int q){

        if (connected(p,q)) {
            System.out.println(p+" and "+q + " are already connected");
            return;
        }

        for (int i =0; i < id.length;i++){
            if (id[i] == find(p)){
                System.out.println("p's parent is " + find(p) + " list item is "+id[i]);
                id[i] =find(q);
            }
        }
    }
    public void print(){

        System.out.print("[");
        for (int i =0; i < id.length; i++){
            System.out.print(id[i]);
            System.out.print(", ");
        }
        System.out.println("]");
    }

    public static void main(String args[]){
        QuickFindUF qfobj = new QuickFindUF(10);
        qfobj.print();
        qfobj.union(3,5);
        qfobj.print();
        qfobj.union(3,8);
        qfobj.print();

    }
}

second (working) attempt

public class QuickFindUF {

    private int[] id;

    public QuickFindUF(int N){
        id = new int[N];
        for (int i = 0;i<N;i++){
            id[i] = i;
        }
    }

    public boolean connected(int p, int q){
        if (id[p] == id[q]){
            return true;
        }
        return false;
    }

    public int find(int x){
        return id[x];
    }

    public void union(int p, int q){

        if (connected(p,q)) {
            System.out.println(p+" and "+q + " are already connected");
            return;
        }

        int pid = find(p);
        int qid = find(q);

        for (int i =0; i < id.length;i++){
            if (id[i] == pid){
                System.out.println("p's parent is " + find(p) + " list item is "+id[i]);
                id[i] =qid;
            }
        }
    }
    public void print(){

        System.out.print("[");
        for (int i =0; i < id.length; i++){
            System.out.print(id[i]);
            System.out.print(", ");
        }
        System.out.println("]");
    }

    public static void main(String args[]){
        QuickFindUF qfobj = new QuickFindUF(10);
        qfobj.print();
        qfobj.union(3,5);
        qfobj.print();
        qfobj.union(3,8);
        qfobj.print();

    }
}

0

There are 0 best solutions below