Try to search your question here, if you can't find : Ask Any Question Now ?

Union Find Disjoint Set algorithm and trying to evaluate data between nodes

HomeCategory: stackoverflowUnion Find Disjoint Set algorithm and trying to evaluate data between nodes
Avatarsourav asked 5 months ago

Sample input:

5 3 
100 
-75 
-25 
-42 
42 
0 1
1 2
3 4

First line = two numbers N, number of people, and M, number of friendships

Following N lines = The amount of debt each person has

The next M lines after that = The friendships

Debt can only be paid off between friends. Given that restriction, output whether or not it’s possible for all possible debts to be forgiven.

For that sample input, the output would be POSSIBLE, because 0-1-2 is a friend group (100 + -75 + -25) and 3-4 is a friend group (-42 + 42).

However, this would not be possible:

4 2
15
20
-10
-25 
0 2 
1 3

I’m taking this to just mean adding up the debt in all the friend groups (using UFDS), and if the sum of any != 0, it’s not possible, else it’s possible.

        int numpeople = reader.nextInt();
        int numfriendships = reader.nextInt();
        int[] debts = new int[numpeople];
        for (int j = 0; j < numpeople; j++) {
            debts[j] = reader.nextInt();
        }

        int[] parent = new int[numpeople];
        for (int j = 0; j < numpeople; j++) {
            parent[j] = j;
        }

        int[] rank = new int[numpeople];
        for (int j = 0; j < numfriendships; j++) {
            int A = reader.nextInt();
            int B = reader.nextInt();
            union(A, B, parent, rank);
        }

        HashMap<Integer, Integer> clusters = new HashMap<Integer, Integer>();
        for (int j = 0; j < parent.length; j++) {
            int curr = parent[j];
            if (!clusters.containsKey(curr)) {
                clusters.put(curr, debts[j]);
            }
            else {
                clusters.put(curr, clusters.get(curr) + debts[j]);
            }
        }
        for (int value : clusters.values()) {
            if (value != 0) {
                System.out.println("IMPOSSIBLE");
                return;
            }
        }
        System.out.println("POSSIBLE");
    }
}

// UFDS find
static int find(int x, int[] parent) {

    if (parent[x]!= x) {
        parent[x] = find(parent[x], parent);
    }

    return parent[x];
}

// UFDS union
static void union(int x, int y, int[] parent, int[] rank) {
    int xRoot = find(x, parent);
    int yRoot = find(y, parent);

    if (xRoot == yRoot) {
        return;
    }
    else {
        if (rank[xRoot] < rank[yRoot]) {
            parent[xRoot] = yRoot;
        }

        else if (rank[yRoot] < rank[xRoot]) {
            parent[yRoot] = xRoot;
        }

        else {
            parent[yRoot] = xRoot;
            for (int i = 0; i < parent.length; i++) {
                if (parent[i] == yRoot) {
                    parent[i] = xRoot;
                }
            }
            rank[xRoot] = rank[xRoot] + 1;
        }
    }
}

This works for the sample input given, but on this online judge thing which runs it through hundreds of test cases, it tells me wrong answer. Not sure where my lapse in thinking is occurring. Maybe something to do with the way I’m comparing with the debts array?

1 Answers
Best Answer
AvatarMannu answered 5 months ago
Your Answer

0 + 18 =

Popular Tags

WP Facebook Auto Publish Powered By : XYZScripts.com