(URI) Componentes Conexos - Solution 2

If you want to see another solution for this problem, click here.

The only difference between this solution and the previous one is related to the method responsible for getting the connected components. Now, the complexity to check the components is O(N) instead of O(N^2).


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

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<ArrayList<Character>> list) throws NumberFormatException, IOException {
        for (int j = 0; j < list.size(); j++) {
            ArrayList<Character> array = list.get(j);
            for (int k = 0; k < array.size(); k++) {
                bw.write(array.get(k) + ",");
            }
            bw.write("\n");
        }
        bw.write(list.size() + " connected components\n\n");
    }
   
    public static ArrayList<ArrayList<Character>> checkComponents(int numVertex) {
        int a = (int)'a';
        ArrayList<ArrayList<Character>> list = new ArrayList<ArrayList<Character>>();
        HashMap<Integer, Integer> mapToList = new HashMap<Integer, Integer>();
        int count = 0;
        for (int j = 1; j <= numVertex; j++) {
            if (!mapToList.containsKey(root(nodeParent[j]))) {
                list.add(count, new ArrayList<Character>());
                list.get(count).add((char)(a+(j-1)));
                mapToList.put(root(nodeParent[j]), count);
                count++;
            }
            else {
                list.get(mapToList.get(root(nodeParent[j]))).add((char)(a+(j-1)));       
            }
        }
       
        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<ArrayList<Character>> 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);
    }
}