(UVA) Ubiquitous Religions - Solução 3

You can check other solutions for this problem here and here.

This solution is different from the previous one (here) because when I connect two people, I change the root in order to link each node directly to its root.


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

class Main  {
    public static Element[] vector;
  
    public static int count() {
        int[] v = new int[vector.length];
        for (int i = 1; i < vector.length; i++) {
            v[root(vector[i].parent)] += 1;
        }
       
        int components = 0;
        for (int i = 1; i < v.length; i++) {
            if (v[i] > 0) {
                components++;
            }
        }
      
        return components;
    }
  
    public static void updateRoot(int p, int rootP) {
        int currNode = p;
        while (vector[currNode].parent != currNode) {
            int oldParent = vector[currNode].parent;
            vector[currNode].parent = rootP; 
            currNode = oldParent;
        }
    }
   
    public static int root(int n) {
        int currNode = n;
        while (vector[currNode].parent != currNode) {
            currNode = vector[currNode].parent;
        }
      
        return currNode;
    }
  
    public static void union(int p1, int p2) {
        int rootP1 = root(p1);
        int rootP2 = root(p2);
       
        if (rootP1 != rootP2) { // they are not connected
            if (vector[rootP1].depth >= vector[rootP2].depth) {
                vector[rootP2].parent = vector[rootP1].parent;
                if (vector[rootP1].depth == vector[rootP2].depth) {
                    vector[rootP1].depth++;
                }
                updateRoot(p1, rootP1); // atualiza root
                updateRoot(p2, rootP1); // atualiza root
            }
            else {
                vector[rootP1].parent = vector[rootP2].parent;
                updateRoot(p2, rootP2); // atualiza root
                updateRoot(p1, rootP2); // atualiza root
            }
        }
    }
  
    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;
    }
}