(UVA) Trust Groups - Solution

I used Kosaraju's algorithm to solve this problem.


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

class Main {
    public static HashMap<String, Integer> map;
    public static HashMap<Integer, ArrayList<Integer>> adjList;
    public static HashMap<Integer, ArrayList<Integer>> adjListReverse;
    public static Deque<Integer> queue;
    public static boolean[] visited;
   
    public static void dfsReverse(int curr) {
        if (visited[curr]) {
            return;
        }
       
        visited[curr] = true;
        ArrayList<Integer> trust = adjListReverse.get(curr);
        for (int i = 0; i < trust.size(); i++) {
            dfsReverse(trust.get(i));
        }
    }
   
    public static void dfs(int curr) {
        if (visited[curr]) {
            return;
        }
       
        visited[curr] = true;
        ArrayList<Integer> trust = adjList.get(curr);
        for (int i = 0; i < trust.size(); i++) {
            dfs(trust.get(i));
        }
        queue.add(curr);
    }
   
    public static 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]);
        while (numPeople != 0 || numConnections != 0) {
            map = new HashMap<String, Integer>();
            adjList = new HashMap<Integer, ArrayList<Integer>>();
            adjListReverse = new HashMap<Integer, ArrayList<Integer>>();
            for (int i = 0; i < numPeople; i++) {
                String name = br.readLine();
                map.put(name, i);
                adjList.put(i, new ArrayList<Integer>());
                adjListReverse.put(i, new ArrayList<Integer>());
            }
           
            for (int i = 0; i < numConnections; i++) {
                String name1 = br.readLine();
                String name2 = br.readLine();
               
                adjList.get(map.get(name1)).add(map.get(name2));
                adjListReverse.get(map.get(name2)).add(map.get(name1));
            }
           
            visited = new boolean[numPeople];
            queue = new ArrayDeque();
            for (int i = 0; i < numPeople; i++) {
                dfs(i);
            }
           
            int count = 0;
            visited = new boolean[numPeople];
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                int curr = queue.pollLast();
                if (!visited[curr]) {
                    dfsReverse(curr);
                    count++;
                }
            }
                   
            System.out.println(count);
           
            line = br.readLine();
            s = line.split("\\s");
            numPeople = Integer.parseInt(s[0]);
            numConnections = Integer.parseInt(s[1]);
        }
                                       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução