(UVA) Beverages - Solution

In order to solve this problem, I used Topological Sorting.

The problem states that "if there is no relation between two beverages, Dilbert should start drink the one that appears first in the input". Then, I used a PriorityQueue.

I also used two maps to map a beverage to an index and this index to the beverage, which helps me during the Topological Sorting.


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

class Main  {
    public static HashMap<String, ArrayList<String>> adjListOut;
    public static HashMap<String, Integer> map;
    public static HashMap<Integer, String> map2;
     
    public static ArrayList<String> topoSort(int numBeverages, int[] degrees) {
        Queue<Integer> zeroDegree = new PriorityQueue<Integer>();
        for (int i = 0; i < numBeverages; i++) {
            if (degrees[i] == 0) {
                zeroDegree.add(i);
            }
        }  
      
        ArrayList<String> sequence = new ArrayList<String>();
        while (zeroDegree.size() > 0) {
            int bev = zeroDegree.poll();
            String beverage = map2.get(bev);
            sequence.add(beverage);
            ArrayList<String> reachBeverages = adjListOut.get(beverage);
            for (int i = 0; i < reachBeverages.size(); i++) {
                String next = reachBeverages.get(i);
                degrees[map.get(next)]--;
                if (degrees[map.get(next)] == 0) {
                    zeroDegree.add(map.get(next));
                }
            }
        }
      
        return sequence;
    }
  
    public static void process() throws NumberFormatException, IOException { 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
        int numCase = 0;
        String line = br.readLine();
        while (line != null) {
            int numBeverages = Integer.parseInt(line);
            adjListOut = new HashMap<String, ArrayList<String>>();
            map = new HashMap<String, Integer>();
            map2 = new HashMap<Integer, String>();
            for (int i = 0; i < numBeverages; i++) {
                String beverage = br.readLine();
                adjListOut.put(beverage, new ArrayList<String>());
                map.put(beverage, i);
                map2.put(i, beverage);
            }
          
            int[] degrees = new int[numBeverages];
          
            line = br.readLine();
            int numConnections = Integer.parseInt(line);
            for (int i = 0; i < numConnections; i++) {
                line = br.readLine();
                String[] beverages = line.split(" ");
                adjListOut.get(beverages[0]).add(beverages[1]);
                degrees[map.get(beverages[1])]++;
            }
          
            ArrayList<String> seq = topoSort(numBeverages, degrees);
            System.out.print("Case #" + ++numCase + ": Dilbert should drink beverages in this order: ");
            for (int i = 0; i < seq.size()-1; i++) {
                System.out.print(seq.get(i) + " ");              
            }
            System.out.println(seq.get(seq.size()-1) + ".\n");
          
            br.readLine(); // blank line after each test
            line = br.readLine();
        }
                                   
        return;
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}