/**
1. 仍然是DAG 判环, 不过要把拓扑序列输出
*/


class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> ins = new HashMap<>();

        for (int i = 0; i < prerequisites.length ; i ++){
            int x = prerequisites[i][1];
            int y = prerequisites[i][0];
            if (graph.get(x) == null) graph.put(x, new HashSet<Integer>());
            graph.get(x).add(y);
            if (ins.get(y) == null) ins.put(y, 0);
            ins.put(y, ins.get(y) + 1);
        }

        int[] res = topSort(graph, ins, numCourses);
        return res;
    }

    int[] topSort(Map<Integer, Set<Integer>> graph, Map<Integer, Integer> ins, int n){
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();

        for (int i = 0 ; i < n ; i++){
            if (ins.get(i) == null){
                queue.offer(i);
            }
        }

        while(!queue.isEmpty()){
            int x = queue.poll();
            list.add(x);

            Set<Integer> edges = graph.get(x);
            if (edges == null) continue;

            for (Integer y : edges){
                ins.put(y, ins.get(y) - 1);
                if(ins.get(y) == 0) queue.offer(y);
            }
        }

        if (list.size() != n) list.clear();
        int[] res = new int[list.size()];
        for (int i = 0 ; i < list.size(); i++) res[i] = list.get(i);
        return res;
    }
}