(UVA) Ubiquitous Religions - Solução 1

In order to solve this problem, I tried to use the Quick-Find (one of the implementations of Union-Find). However, once the complexity for the union method is O(N), and it could be O(N^2) (1 <= N <= 50000) calls to union, I had to implement the Weighted Quick-Union.

Although I have studied about Union-Find in the class "Algorithms, Part I", from Coursera (you can find more details here and here), I used my own implementation to solve this problem.


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

class Main  { 
    public static Element[] vector;
   
    public static int count() {
        ArrayList<Integer> array = new ArrayList<Integer>();
        int c = 0;
        for (int i = 1; i < vector.length; i++) {
            if (!array.contains(root(vector[i].parent))) {
                array.add(root(vector[i].parent));
                c++;
            }
        }
       
        return c;
    }
   
    public static int root(int n) {
        int currNode = n;
        while (vector[currNode].parent != currNode) {
            currNode = vector[currNode].parent;
        }
       
        return currNode;
    }
   
    public static boolean connected(int p1, int p2) {
        if (root(p1) == root(p2)) {
            return true;
        }

        return false;
    }
   
    public static void union(int p1, int p2) {
        if (!connected(p1, p2)) {
            int rootP1 = root(p1);
            int rootP2 = root(p2);
           
            if (vector[rootP1].depth >= vector[rootP2].depth) {
                vector[rootP2].parent = vector[rootP1].parent;
                if (vector[rootP1].depth < vector[rootP2].depth+1) {
                    vector[rootP1].depth = vector[rootP2].depth+1;
                }
            }
            else {
                vector[rootP1].parent = vector[rootP2].parent;
                if (vector[rootP2].depth < vector[rootP1].depth+1) {
                    vector[rootP2].depth = vector[rootP1].depth+1;
                }
            }
        }
    }
   
    public static void readEntries(BufferedReader br, int numPairs) throws NumberFormatException, IOException {
        for (int i = 0; i < numPairs; i++) {
            int p1 = reader(br);
            int p2 = reader(br);
            union(p1, p2);
        }
    }
   
    public static void initVector(int numPeople) {
        vector = new Element[numPeople+1];
        for (int i = 1; i <= numPeople; i++) {
            Element e = new Element(i, 0);
            vector[i] = e;
        }
    }
   
    static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;      
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            }
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp;     
    }
   
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numPeople = reader(br);
        int numPairs = reader(br);
        int numCase = 1;

        while (numPeople != 0 || numPairs != 0) {
            vector = new Element[numPeople+1];
            initVector(numPeople);
           
            readEntries(br, numPairs);
               
            System.out.println("Case " + numCase++ + ": " + count());
       
            numPeople = reader(br);
            numPairs = reader(br);
        }
               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Element {
    int parent;
    int depth;
   
    public Element(int parent, int depth) {
        this.parent = parent;
        this.depth = depth;
    }
}