(URI) Componentes Conexos - Solution 1

I used the Union-Find approach to solve this problem.

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

class Main  {
    public static HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    public static int[] nodeParent;
    public static int[] depth;
   
    public static void printAnswer(BufferedWriter bw, ArrayList<String> list) throws NumberFormatException, IOException {
        for (int j = 0; j < list.size(); j++) {
            for (int k = 0; k < list.get(j).length(); k++) {
                bw.write(list.get(j).charAt(k) + ",");
            }
            bw.write("\n");
        }
        bw.write(list.size() + " connected components\n\n");
    }
           
    public static ArrayList<String> checkComponents(int numVertex) {
        ArrayList<Integer> roots = new ArrayList<Integer>();
        for (int i = 1; i <= numVertex; i++) {
            if (!roots.contains(root(nodeParent[i]))) {
                roots.add(root(nodeParent[i]));
            }
        }
       
        int a = (int)'a';
        ArrayList<String> list = new ArrayList<String>();
        for (int i = 0; i < roots.size(); i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 1; j <= numVertex; j++) {
                if (roots.get(i) == root(nodeParent[j])) {
                    sb.append((char)(a+(j-1)));  
                }
            }
            list.add(sb.toString());
        }
       
        return list;
    }
   
    public static int root(int n) {
        int currNode = n;
        while (nodeParent[currNode] != currNode) {
            currNode = nodeParent[currNode];
        }
       
        return currNode;
    }
   
    public static void union(int n1, int n2) {
        int rootN1 = root(n1);
        int rootN2 = root(n2);
       
        if (rootN1 != rootN2) {
            if (depth[rootN1] >= depth[rootN2]) {
                nodeParent[rootN2] = nodeParent[rootN1];
                if (depth[rootN1] == depth[rootN2]) {
                    depth[rootN1]++;
                }
            }
            else {
                nodeParent[rootN1] = nodeParent[rootN2];
            }
        }
    }
       
    public static void readConnections(BufferedReader br, int numEdges) throws NumberFormatException, IOException {
        for (int j = 0; j < numEdges; j++) {
            String line = br.readLine();
            char node1 = line.charAt(0);;
            char node2 = line.charAt(2);;
            union(map.get(node1), map.get(node2));
        }
    }
   
    public static void initArrays(int numVertex) {
        int a = (int)'a';
        for (int j = 0; j < numVertex; j++) {
            map.put((char)(a+j), (j+1));
            nodeParent[j+1] = j+1;
            depth[j+1] = 0;
        }
    }
   
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numCases = Integer.parseInt(br.readLine());
        for (int i = 0; i < numCases; i++) {
            String line = br.readLine();
            StringTokenizer st = new StringTokenizer(line);
            int numVertex = Integer.parseInt(st.nextToken());
            int numEdges = Integer.parseInt(st.nextToken());
           
            nodeParent = new int[numVertex+1];
            depth = new int[numVertex+1];
           
            initArrays(numVertex);
           
            readConnections(br, numEdges);
           
            bw.write("Case #" + (i+1) + ":\n");
            ArrayList<String> list = checkComponents(numVertex);
            printAnswer(bw, list);
        }
       
        bw.flush();
        bw.close();
               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}