(UVA) Friends - Solução 1

Similarly to what I did in the problem "Ubiquitous Religions", I used the Union-Find approach to solve this problem.

For this problem, instead of using another class to keep one node's parent and its depth, I am using two arrays (one array to keep the node's parent, and the other one to keep the depth). It simplifies some operations along the code. 

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[] parentNode;
    public static int[] depth;
   
    public static int countOccurrences() {
        int[] v = new int[parentNode.length];
       
        for (int i = 1; i < parentNode.length; i++) {
            v[root(parentNode[i])] += 1;
        }
       
        int occurrences = -1;
        for (int i = 1; i < v.length; i++) {
            if (v[i] > occurrences) {
                occurrences = v[i];
            }
        }
       
        return occurrences;
    }
   
    public static int root(int p1) {
        int curr = p1;
        while (parentNode[curr] != curr) {
            curr = parentNode[curr];
        }
       
        return curr;
    }
       
    public static void union(int p1, int p2) {
        int rootP1 = root(p1);
        int rootP2 = root(p2);
       
        if (rootP1 != rootP2) { // they are not connected
            if (depth[rootP1] >= depth[rootP2]) {
                parentNode[rootP2] = parentNode[rootP1];
                if (depth[rootP1] < depth[rootP2]+1) {
                    depth[rootP1] = depth[rootP2]+1;
                }
            }
            else {
                parentNode[rootP1] = parentNode[rootP2];
                if (depth[rootP2] < depth[rootP1]+1) {
                    depth[rootP2] = depth[rootP1]+1;
                }
            }
        }
    }
   
    public static void readEntries(BufferedReader br, int numPairs) throws NumberFormatException, IOException {
        for (int j = 0; j < numPairs; j++) {
            int p1 = reader(br);
            int p2 = reader(br);
           
            union(p1, p2);
        }
    }
   
    public static void initVectors(int numPeople) {
        for (int i = 1; i <= numPeople; i++) {
            parentNode[i] = i;
            depth[i] = 0;
        }
    }
   
    public 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 numCases = reader(br);
        for (int i = 0; i < numCases; i++) {   
            int numPeople = reader(br);
            int numPairs = reader(br);
           
            parentNode = new int[numPeople+1];
            depth = new int[numPeople+1];
            initVectors(numPeople);
           
            readEntries(br, numPairs);
           
            System.out.println(countOccurrences());
        }
               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}