(UVA) Nature - Solution

In order to solve this problem, I implemented the Weighted Quick-Union.

I used a HashMap structure to map each creature to a number from 1 to numCreatures. Therefore, when I call the union method for two creatures, I only need to get the two numbers related to the creatures.

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 int[] nodeParent;
    public static int[] depth;
    public static HashMap<String, Integer> creatures;
  
    public static int count() {
        int[] v = new int[nodeParent.length];
      
        for (int i = 1; i < nodeParent.length; i++) {
            v[root(nodeParent[i])] += 1;
        }
      
        int biggerOccurrence = -1;
        for (int i = 1; i < v.length; i++) {
            if (v[i] > biggerOccurrence) {
                biggerOccurrence = v[i];
            }
        }
      
        return biggerOccurrence;
    }
  
    public static int root(int node) {
        int currNode = node;
        while (nodeParent[currNode] != currNode) {
            currNode = nodeParent[currNode];
        }
              
        return currNode;
    }
  
    public static void union(int node1, int node2) {
        int rootN1 = root(node1);
        int rootN2 = root(node2);

        if (rootN1 != rootN2) { // they are not connected
            if (depth[rootN1] >= depth[rootN2]) {
                nodeParent[rootN2] = nodeParent[rootN1];
                if (depth[rootN1] == depth[rootN2]) {
                    depth[rootN1] += 1; // link between rootN1 and rootN2
                }
            }
            else {
                nodeParent[rootN1] = nodeParent[rootN2];
            }
        }
    }
  
    public static void initArrays(int numCreatures) {
        for (int i = 1; i <= numCreatures; i++) {
            nodeParent[i] = i;
            depth[i] = 0;
        }
    }
  
    public static void initHashMap(Scanner sc, int numCreatures) {
        for (int i = 1; i <= numCreatures; i++) {
            String s = sc.next();
            creatures.put(s, i);
        }
    }
  
    public static void process() throws NumberFormatException, IOException {  
        Scanner sc = new Scanner(System.in);
      
        int numCreatures = sc.nextInt();
        int numRelations = sc.nextInt();
      
        while (numCreatures != 0 || numRelations != 0) {
            nodeParent = new int[numCreatures+1];
            depth = new int[numCreatures+1];
          
            initArrays(numCreatures);
          
            creatures = new HashMap<String, Integer>();
            initHashMap(sc, numCreatures); 
          
            for (int i = 1; i <= numRelations; i++) {
                String creat = sc.next(); // creature
                String pred = sc.next(); // predator
              
                union(creatures.get(creat), creatures.get(pred));
            }
          
            System.out.println(count());
          
            numCreatures = sc.nextInt();
            numRelations = sc.nextInt();
        }
                      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}