(SPOJ) Fusões - Solution

Link to the problem: http://br.spoj.com/problems/FUSOES1/

The solution below used Union-Find to connect two banks. Then, when it was necessary to check if two banks were the same, we only had to check their roots.


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

class Main {
    public int[] nodeParent;
    public int[] depth;
   
    public int root(int n) {
        while (nodeParent[n] != n) {
            n = nodeParent[n];
        }
       
        return n;
    }
   
    public void union(int n1, int n2) {
        int rootN1 = root(n1);
        int rootN2 = root(n2);
       
        if (rootN1 != rootN2) {
            if (depth[rootN1] >= depth[rootN2]) {
                nodeParent[rootN2] = nodeParent[rootN1];
                if (depth[rootN1] == depth[rootN2]) {
                    depth[rootN1] += 1;
                }
            }
            else {
                nodeParent[rootN1] = nodeParent[rootN2];
            }
        }
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line = br.readLine();
        String[] s = line.split(" ");
        int numBanks = Integer.parseInt(s[0]);
        int numOp = Integer.parseInt(s[1]);
       
        nodeParent = new int[numBanks+1];
        depth = new int[numBanks+1];
        for (int i = 1; i <= numBanks; i++) {
            nodeParent[i] = i;
            depth[i] = 0;
        }
       
        for (int i = 0; i < numOp; i++) {
            line = br.readLine();
            s = line.split(" ");
           
            char c = s[0].charAt(0);
            int bank1 = Integer.parseInt(s[1]);
            int bank2 = Integer.parseInt(s[2]);
           
            if (c == 'F') {
                union(bank1, bank2);
            }
            else {
                if (root(bank1) == root(bank2)) {
                    bw.write("S\n");
                }
                else {
                    bw.write("N\n");
                }
            }
        }
       
        bw.flush();
        br.close();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}