Order Dependency

Given a list of OrderDependency, one OrderDependency includes two Order, like[pre, cur], Order pre must be done first, then Order cur can be done. Return a list of Order according to the given OrderDependency. If it is impossible to complete all the Order, return an empty list.

For example:
Given: [["0", "1"], ["1", "2"],["2", "3"],["3", "4"]], return: ["0", "1", "2", "3"].

/*
This problem can be reduce to the topological sort problem. 
Use one hashmap to store each Order and its in-degrees. Use another hashmap to store the Orders pointed by one pre Order. After the initialization, find Orders with 0 in-degrees, they are the fist Orders that should be completed. And then use bfs to find the other Orders level by level that with 0 in-degrees.

The trap here is that there will be some different Orders but have the same orderName. We should consider they are the same. So, we should make orderName be the key when using hashmap.

time:O(n), space:O(n)
*/

import java.util.*;

class Order{
    String orderName;
    public Order(String string){
        this.orderName = string;
    }
}
class OrderDependency{
    Order cur;
    Order pre;
    public OrderDependency(Order pre, Order cur){
        this.pre = pre;
        this.cur = cur;
    }
}
public class Solution {
    public static List<Order> solution(List<OrderDependency>                                                 orderDependencies) {
        List<Order> ans = new ArrayList<>();
        if (orderDependencies == null || 
            orderDependencies.size() == 0) {
            return ans;
        } 
        Map<String, Integer> inMap = new HashMap<>();
        Map<String, List<String>> outMap = new HashMap<>();
        for (OrderDependency od : orderDependencies) {
            Order cur = od.cur;
            Order pre = od.pre;
            String curName = cur.orderName;
            String preName = pre.orderName;
            if (!inMap.containsKey(curName)) {
                inMap.put(curName, 1);
            } else {
                inMap.put(curName, inMap.get(curName) + 1);
            }
            if (!inMap.containsKey(preName)) {
                inMap.put(preName, 0);
            }

            if (!outMap.containsKey(preName)) {
                List<String> list = new ArrayList<>();
                list.add(curName);
                outMap.put(preName, list);
            } else {
                outMap.get(preName).add(curName);
            }
        }
        Queue<String> queue = new LinkedList<>();
        for (Map.Entry<String, Integer> entry : inMap.entrySet()) {
            if (entry.getValue() == 0) {
                queue.add(entry.getKey());
                ans.add(new Order(entry.getKey()));
            }
        }
        while (!queue.isEmpty()) {
            String preName = queue.poll();
            if (!outMap.containsKey(preName)) {
                continue;
            }
            for (String curName : outMap.get(preName)) {
                inMap.put(curName, inMap.get(curName) - 1);
                if (inMap.get(curName) == 0) {
                    ans.add(new Order(curName));
                    queue.add(curName);
                }
            }
        }
        if (ans.size() != inMap.size()) {
            return new ArrayList<Order>();
        }
        return ans;       
    }

    public static void main(String[] args) {
        Order o1 = new Order("A");
        Order o2 = new Order("A");
        Order o3 = new Order("C");
        Order o4 = new Order("B");
        Order o5 = new Order("C");
        Order o6 = new Order("A");
        Order o7 = new Order("B");
        Order o8 = new Order("C");
        Order o9 = new Order("D");
        OrderDependency od1 = new OrderDependency(o1, o3);
        OrderDependency od2 = new OrderDependency(o2, o7);
        OrderDependency od3 = new OrderDependency(o3, o9);
        OrderDependency od4 = new OrderDependency(o4, o3);
        OrderDependency od5 = new OrderDependency(o6, o9);
        OrderDependency od6 = new OrderDependency(o8, o9);
        OrderDependency od7 = new OrderDependency(o2, o5);

        OrderDependency od8 = new OrderDependency(o1, o4);
        OrderDependency od9 = new OrderDependency(o4, o3);
        OrderDependency od10 = new OrderDependency(o3, o9);
        OrderDependency od11 = new OrderDependency(o9, o2);

        List<OrderDependency> list = new ArrayList<>();
        list.add(od1);
        list.add(od2);
        list.add(od3);
        list.add(od4);
        list.add(od5);
        list.add(od6);
        list.add(od7);

        List<OrderDependency> list2 = new ArrayList<>();
        list2.add(od8);
        list2.add(od9);
        list2.add(od10);
        list2.add(od11);

        List<Order> res = solution(list);
        List<Order> res2 = solution(list2);

        System.out.println("res: should print: A -> B -> C -> D");
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i).orderName);
            if (i+1 < res.size()){
                System.out.print(" -> ");
            }
        }
        System.out.println("");
        System.out.println("res2: should print nothing, because of                               the cycle in the graph");
        for (int i = 0; i < res2.size(); i++) {
            System.out.print(res2.get(i).orderName);
            if (i+1 < res2.size()){
                System.out.print(" -> ");
            }
        }
    }
}