(UVA) Graph Connectivity - Solution 2

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

I used Depth-First Search to solve this problem.


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

class Main {
    public static HashMap<Integer, ArrayList<Integer>> adjList;
    public static boolean[] visited;
   
    public static void dfs(int node) {
        if (visited[node]) {
            return;
        }
       
        visited[node] = true;
        ArrayList<Integer> reachNodes = adjList.get(node);
        for (int i = 0; i < reachNodes.size(); i++) {
            dfs(reachNodes.get(i));
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        int numCases = Integer.parseInt(line);
        line = br.readLine(); // blank line
        for (int i = 0; i < numCases; i++) {
            if (i > 0) {
                System.out.println();
            }
           
            String max = br.readLine();
            int numNodes = max.charAt(0)-'A'+1;
            adjList = new HashMap<Integer, ArrayList<Integer>>();
            for (int j = 0; j < numNodes; j++) {
                adjList.put(j, new ArrayList<Integer>());
            }
           
            line = br.readLine();
            while (!line.equals("")) {
                char c1 = line.charAt(0);
                char c2 = line.charAt(1);
                adjList.get(c1-'A').add(c2-'A');
                adjList.get(c2-'A').add(c1-'A');
               
                line = br.readLine(); 
                if (line == null) {
                    break;
                }             
            }
           
            int count = 0;
            visited = new boolean[numNodes];
            for (int j = 0; j < numNodes; j++) {
                if (visited[j]) {
                    continue;
                }
                dfs(j);
                count++;
            }
           
            System.out.println(count);
        }
                                               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}