(SPOJ) Famílias de Troia - Solution

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

For this problem, we need to determine the amount of distinct families. First, we can map the entries into an adjacency list. Then, we call the Breadth-First Search (BFS) method, which will visit all the members of a specific family. Finally, we only need to count how many times the BFS method was called, and we will know how many distinct families there are.


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

class Main {
    public HashMap<Integer, ArrayList<Integer>> adjList;
    public HashSet<Integer> visited;
   
    public void bfs(int curr) {
        Queue<Integer> queue = new ArrayDeque<Integer>();
        queue.add(curr);
       
        while (queue.size() > 0) {
            int currPerson = queue.poll();
           
            if (visited.contains(currPerson)) {
                continue;
            }
            visited.add(currPerson);

            ArrayList<Integer> parents = adjList.get(currPerson);
            for (int i = 0; i < parents.size(); i++) {
                queue.add(parents.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 numPeople = Integer.parseInt(s[0]);
        int numConnections = Integer.parseInt(s[1]);
       
        adjList = new HashMap<>();
        for (int i = 1; i <= numPeople; i++) {
            adjList.put(i, new ArrayList<Integer>());
        }
       
        for (int i = 0; i < numConnections; i++) {
            line = br.readLine();
            s = line.split("\\s");
            int p1 = Integer.parseInt(s[0]);
            int p2 = Integer.parseInt(s[1]);
            adjList.get(p1).add(p2);
            adjList.get(p2).add(p1);
        }
       
        int count = 0;
        visited = new HashSet<>();
        for (int i = 1; i <= numPeople; i++) {
            if (visited.contains(i)) {
                continue;
            }
            bfs(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);
    }
}