CODEWITHSUNDEEP
javaeclipsealgorithm
Hat
Hat

Reputation: 1731

weighted union find algorithm

I'm new to java and I have a weighted union find algorithm. When I run this code in eclipse on a scrapbook page, it keeps evaluating forever.

java code

public class weightedUF {
    private int[] id;
    private int[] sz;

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

    private int root(int i) {
        while (i != id[i]) {
            i = id[i];
        }
        return i;
    }

    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }

    public void union(int p, int q) {
        int i = root(p);
        int j = root(q);
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        }
        else {
            id[j] = i;
            sz[i] += sz[j];
        }
        id[i] = j;
    }
}

scrapbook test code

weightedUF union = new weightedUF(10);
union.union(9, 2);
union.union(5, 2);
union.union(1, 8);
union.union(5, 7);
union.union(4, 3);
union.union(0, 7);
union.union(1, 3);
union.union(2, 4);
union.union(8, 6);
union

Upvotes: 3

Views: 1798

Answers (1)

Orab&#238;g
Orab&#238;g

Reputation: 12002

I think you should remove your last line :

 id[i] = j;

it's corrupting your id array.

Upvotes: 3

Related Questions