(SPOJ) Gincana - Solution 1

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

We need to find all the different teams that are possible to create. Each group of friends compose a team. Then, the solution below uses the Union-Find approach to separate each group of friends. In the end, it is only necessary to count how many connected components we have.


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

class Main {
    public int[] nodeParent;
    public int[] depth;
   
    public int count(int numStudents) {
        int[] rootArray = new int[numStudents+1];
        for (int i = 1; i <= numStudents; i++) {
            rootArray[root(nodeParent[i])]++;
        }
       
        int countDiffRoot = 0;
        for (int i = 1; i <= numStudents; i++) {
            if (rootArray[i] != 0) {
                countDiffRoot++;
            }
        }
       
        return countDiffRoot;
    }
   
    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) {
            return;
        }
       
        if (depth[rootN1] >= depth[rootN2]) {
            nodeParent[rootN2] = nodeParent[rootN1];
            if (depth[rootN1] == depth[rootN2]) {
                depth[rootN1]++;
            }
        }
        else {
            nodeParent[rootN1] = nodeParent[rootN2];
        }
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        String[] s = line.split("\\s");
        int numStudents = Integer.parseInt(s[0]);
        int numLines = Integer.parseInt(s[1]);
       
        nodeParent = new int[numStudents+1];
        depth = new int[numStudents+1];
        for (int i = 1; i <= numStudents; i++) {
            nodeParent[i] = i;
            depth[i] = 0;
        }
       
        for (int i = 0; i < numLines; i++) {
            line = br.readLine();
            s = line.split("\\s");
           
            int st1 = Integer.parseInt(s[0]);
            int st2 = Integer.parseInt(s[1]);
            union(st1, st2);
        }
       
        System.out.println(count(numStudents));
                          
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}