(UVA) Test - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1672

In the output of this problem, we need to present a set of answers, where contradictory answers need to be in the same set. Contradictory answers are those that compose a cycle ("the answers may indicate a preference for X over Y and also for Y over X"). Therefore, the solution below is using Kosaraju's algorithm to solve this problem.

Kosaraju is one of the algorithms used to find strongly connected components.


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

class Main {
    public HashMap<Character, ArrayList<Character>> adjListOut;
    public HashMap<Character, ArrayList<Character>> adjListOutReverse;
    public Deque<Character> stack;
    public HashSet<Character> visited;
    public HashMap<Character, Integer> identities;
   
    public void dfsReverse(Character c, int idt) {
        if (visited.contains(c)) {
            return;
        }
       
        identities.put(c, idt);
       
        visited.add(c);
        ArrayList<Character> reachLetters = adjListOutReverse.get(c);
        for (int i = 0; i < reachLetters.size(); i++) {
            dfsReverse(reachLetters.get(i), idt);
        }
    }
   
    public void dfs(Character c) {
        if (visited.contains(c)) {
            return;
        }
       
        visited.add(c);
        ArrayList<Character> reachLetters = adjListOut.get(c);
        for (int i = 0; i < reachLetters.size(); i++) {
            dfs(reachLetters.get(i));
        }
        stack.add(c);
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        int numCases = 0;
        int numQuestions = sc.nextInt();
        while (numQuestions != 0) {
            if (numCases > 0) {
                System.out.println();
            }
            sc.nextLine();
           
            adjListOut = new HashMap<>();
            adjListOutReverse = new HashMap<>();
            HashSet<Character> letters = new HashSet<>();
           
            // read entries
            for (int i = 0; i < numQuestions; i++) {
                char[] options = new char[5];
                String line = sc.nextLine();
                String[] s = line.split("\\s");
                for (int j = 0; j < 5; j++) {
                    char c = s[j].charAt(0);
                    options[j] = c;
                    letters.add(c);
                    if (!adjListOut.containsKey(c)) {
                        adjListOut.put(c, new ArrayList<Character>());
                    }
                    if (!adjListOutReverse.containsKey(c)) {
                        adjListOutReverse.put(c, new ArrayList<Character>());
                    }
                }
                char answer = s[5].charAt(0);
                // fill adjacency list (chosen letter points to other letters)
                for (int j = 0; j < 5; j++) {
                    if (options[j] == answer) {
                        continue;
                    }
                    adjListOut.get(answer).add(options[j]);
                    adjListOutReverse.get(options[j]).add(answer);
                }
            }
           
            /* begin Kosaraju */
            visited = new HashSet<>();
            stack = new ArrayDeque<>();
            Iterator it = letters.iterator();
            while (it.hasNext()) {
                dfs((Character)it.next());
            }
           
            int idt = 0;
            int stackSize = stack.size();
            visited = new HashSet<>();
            identities = new HashMap<>();
            for (int i = 0; i < stackSize; i++) {
                Character c = stack.pollLast();
                if (!visited.contains(c)) {
                    dfsReverse(c, idt);
                    idt++;
                }
            }
            int maxIdt = idt;
            /* end Kosaraju */
           
            HashMap<Integer, TreeSet<Character>> mapIdt = new HashMap<>();
            // letters with the same idt (same connected component) will be in
            // the same structure
            for (int i = maxIdt-1; i >= 0; i--) {
                mapIdt.put(i, new TreeSet<Character>());
                for (Character c : identities.keySet()) {
                    if (identities.get(c) == i) {
                        mapIdt.get(i).add(c);
                    }
                }
            }
           
            TreeSet<String> answer = new TreeSet<>();
            // manage to show the answer in lexicographic order
            for (int i = maxIdt-1; i >= 0; i--) {
                StringBuilder sb = new StringBuilder();
                int size = mapIdt.get(i).size();
                for (int j = 0; j < size; j++) {
                    sb.append(mapIdt.get(i).pollFirst());
                    if (j == size-1) {
                        continue;
                    }
                    sb.append(" ");
                }
                answer.add(sb.toString());               
            }
           
            for (int i = 0; i < maxIdt; i++) {
                System.out.println(answer.pollFirst());
            }
           
            numCases++;
            numQuestions = sc.nextInt(); 
        }
                                       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}