/**
1. 本质上还是判断DAG是否有环, 不过本题不要求图连通, 所以直接判断拓扑路径的长度是否等于n即可
*/


class Solution {
    public boolean canFinish(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][0];
            int y = prerequisites[i][1];
            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);
        } 
        return topSort(graph, ins, numCourses);
    }


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

        for (int i= 0 ; i < n ; i++){
            if (ins.get(i) == null){
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()){
            int top = queue.poll();
            result.add(top);
            Set<Integer> edges = graph.get(top);
            if (edges == null) continue;
            for (Integer y : edges){
                ins.put(y, ins.get(y) - 1);
                if (ins.get(y) == 0) queue.offer(y);
            }
        }
        return n == result.size();
    }
}