(SPOJ) Gincana - Solution 2

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

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

This solution used Depth-First Search to solve this problem. Given a student, we call the DFS method in order to find all the students that are related to him/her. Then, a whole group of friends will be covered by each call to the DFS method, which give us the answer to this problem.


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

class Main {
    public HashMap<Integer, ArrayList<Integer>> adjList;
    public boolean[] visited;
   
    public void dfs(int currStudent) {
        if (visited[currStudent]) {
            return;
        }
       
        visited[currStudent] = true;
        ArrayList<Integer> friends = adjList.get(currStudent);
        for (int i = 0; i < friends.size(); i++) {
            dfs(friends.get(i));
        }
    }
   
    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]);
       
        adjList = new HashMap<>();
        for (int i = 1; i <= numStudents; i++) {
            adjList.put(i, new ArrayList<Integer>());
        }
       
        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]);
            adjList.get(st1).add(st2);
            adjList.get(st2).add(st1);
        }
       
        int count = 0;
        visited = new boolean[numStudents+1];
        for (int i = 1; i <= numStudents; i++) {
            if (visited[i]) {
                continue;
            }
            dfs(i);
            count++;
        }
       
        System.out.println(count);
                          
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}