(UVA) Ordering - Solution

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

The solution below used a mix of Topological Sorting and Backtracking to solve this problem.


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

class Main  {
    public HashMap<Character, ArrayList<Character>> dependents;
    public ArrayList<Character> sequence;
    public boolean[] considered;
    public int numConsidered;
    public int[] degrees;
    public ArrayList<Character> zeroDegree;
    public int totalLetters;
    public TreeSet<String> answer;
    public String[] letters;
 
    public void rec() {
        if (numConsidered == letters.length) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < sequence.size()-1; i++) {
                sb.append(sequence.get(i)+" ");
            }
            sb.append(sequence.get(sequence.size()-1));
            answer.add(sb.toString());
            return;
        }
     
        for (int i = 0; i < zeroDegree.size(); i++) { // try all the nodes that are available (have degree equals to zero)
            if (considered[i]) {
                continue;
            }
            numConsidered++;
            considered[i] = true;
            Character curr = zeroDegree.get(i);
            sequence.add(curr);
            ArrayList<Character> reachable = dependents.get(curr);
            for (int j = 0; j < reachable.size(); j++) {
                degrees[reachable.get(j)-'A']--;
                if (degrees[reachable.get(j)-'A'] == 0) { // if the node is free (degree is equal to zero)
                    zeroDegree.add(reachable.get(j));
                }
            }
            rec();
            for (int j = 0; j < reachable.size(); j++) {
                degrees[reachable.get(j)-'A']++;
                if (degrees[reachable.get(j)-'A'] == 1) { // if the node was free (degree was equal to zero)
                    zeroDegree.remove(zeroDegree.size()-1);
                }
            }
            sequence.remove(sequence.size()-1);
            considered[i] = false;
            numConsidered--;
        }
    }
 
    public void process() throws NumberFormatException, IOException { 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
     
        int numCases = Integer.parseInt(br.readLine());
        for (int test = 0; test < numCases; test++) {
            if (test > 0) {
                bw.write("\n"); // blank line between outputs
            }
     
            String line = br.readLine();
            line = br.readLine();
            letters = line.split(" ");

            degrees = new int[26];
            Arrays.fill(degrees, -1);

            dependents = new HashMap<>();
            for (int i = 0; i < letters.length; i++) {
                dependents.put(letters[i].charAt(0), new ArrayList<Character>());
                degrees[letters[i].charAt(0)-'A'] = 0;
            }
         
            // read dependencies
            line = br.readLine();
            String[] d = line.split(" ");
            for (int i = 0; i < d.length; i++) {
                String[] s = d[i].split("<");
                degrees[s[1].charAt(0)-'A']++;
                dependents.get(s[0].charAt(0)).add(s[1].charAt(0));         
            }
         
            // get all the nodes that have degree equals to zero
            zeroDegree = new ArrayList<>();
            for (int i = 0; i < degrees.length; i++) {
                if (degrees[i] != 0) {
                    continue;
                }
                zeroDegree.add((char)(i+'A'));
            }
         
            numConsidered = 0;
            considered = new boolean[letters.length];
            sequence = new ArrayList<>();
            answer = new TreeSet<>();
            rec();
         
            if (answer.size() > 0) {
                for (String s : answer) {
                    bw.write(s+"\n");             
                }
            }
            else {
                bw.write("NO\n");
            }
        }
     
        bw.flush();
        bw.close();
     
        return;
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}