Order Dependency

2017-09-14  本文已影响0人  Wenyue_offer
import java.util.*;
class Order{
    String orderName;
    public Order(String orderName)
    {
        this.orderName = orderName;
    }
}
class OrderDependency{
    Order order;
    Order dependent;
    public OrderDependency(Order order, Order dependent)
    {
        this.order = order;
        this.dependent = dependent;
    }
}
public class Solution {
    public static List<Order> findOrder(List<OrderDependency> depenency)
    {
        Map<String, Integer> inmap = new HashMap<>();
        Map<String, List<String>> outmap = new HashMap<>();
        for(OrderDependency i: depenency)
        {
            if(!inmap.containsKey(i.dependent.orderName)) inmap.put(i.dependent.orderName, 0);
            if(!inmap.containsKey(i.order.orderName)) inmap.put(i.order.orderName, 0);
            inmap.put(i.order.orderName, inmap.get(i.order.orderName) + 1);
            if(!outmap.containsKey(i.dependent.orderName)) outmap.put(i.dependent.orderName, new ArrayList<String>());
            outmap.get(i.dependent.orderName).add(i.order.orderName);
        }
        List<Order> res = new ArrayList<>();
        Queue<String> queue = new LinkedList<>();
        for(String i: inmap.keySet())
        {
            if(inmap.get(i) == 0) queue.offer(i);
        }
        while(!queue.isEmpty())
        {
            String s = queue.poll();
            res.add(new Order(s));
            if(outmap.containsKey(s))
            {
                for(String o: outmap.get(s))
                {
                    inmap.put(o, inmap.get(o) - 1);
                    if(inmap.get(o) == 0) queue.offer(o);
                }
            }
            outmap.remove(s);
        }
        return res;
    }
    public static void main(String[] args)
    {
        List<OrderDependency> input = new ArrayList<>();
        input.add(new OrderDependency(new Order("A"), new Order("E")));
        input.add(new OrderDependency(new Order("D"), new Order("E")));
        input.add(new OrderDependency(new Order("A"), new Order("C")));
        input.add(new OrderDependency(new Order("B"), new Order("D")));
        List<Order> output = findOrder(input);
        for(Order i: output) System.out.print(i.orderName + " ");
    }
}

上一篇 下一篇

猜你喜欢

热点阅读