(UVA) Money Matters - Solution

I used the Union-Find approach to solve this problem.

I had to use two additional arrays. One of them was used to keep the amount of money that a friend f owed or was owed. The other one was used to keep the sum of the amount of money inside a circle of friends. Then, if the sum of money inside each circle of friends was equal to zero, there was no debt.

import java.io.*;
import java.util.*;

class Main  {
    public static int[] nodeParent;
    public static int[] depth;
    public static int[] owesOwed;
    public static int[] money;
   
    public static boolean verify(int numFriends) {
        for (int i = 0; i < numFriends; i++) {
            money[root(nodeParent[i])] += owesOwed[i];
        }
       
        for (int i = 0; i < numFriends; i++) {
            if (money[i] != 0) {
                return false;
            }
        }
       
        return true;
    }
   
    public static int root(int n) {
        int currNode = n;
        while (nodeParent[currNode] != currNode) {
            currNode = nodeParent[currNode];
        }
       
        return currNode;
    }
   
    public static void union(int n1, int n2) {
        int rootN1 = root(n1);
        int rootN2 = root(n2);

        if (rootN1 != rootN2) { // they are not connected
            if (depth[rootN1] >= depth[rootN2]) {
                nodeParent[rootN2] = nodeParent[rootN1];
                if (depth[rootN1] == depth[rootN2]) {
                    depth[rootN1]++; // link between rootN1 and rootN2
                }   
            }
            else {
                nodeParent[rootN1] = nodeParent[rootN2];
            }
        }
    }
   
    public static void readFriendships(BufferedReader br, int numFriendships) throws NumberFormatException, IOException {
        for (int j = 0; j < numFriendships; j++) {
            int f1 = reader(br);
            int f2 = reader(br);
            union(f1, f2);
        }
    }
               
    public static void initArrays(BufferedReader br, int numFriends) throws NumberFormatException, IOException {
        for (int j = 0; j < numFriends; j++) {
            nodeParent[j] = j;
            depth[j] = 0;
            owesOwed[j] = reader(br);
            money[j] = 0;
        }
    }   
   
    static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;     
        int sinal = 1;     
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            }
            if (n == '-') {
                sinal = -1;
            }         
            if (n == '+') {
                sinal = 1;
            }    
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp*sinal;     
    }
   
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numCases = reader(br);
        for (int i = 0; i < numCases; i++) {
            int numFriends = reader(br);
            int numFriendships = reader(br);
           
            nodeParent = new int[numFriends];
            depth = new int[numFriends];
            owesOwed = new int[numFriends];
            money = new int[numFriends];
            initArrays(br, numFriends);
           
            readFriendships(br, numFriendships);
           
            if (verify(numFriends)) {
                System.out.println("POSSIBLE");
            }
            else {
                System.out.println("IMPOSSIBLE");
            }
        }
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}