There are a total ofncourses you have to take, labeled from0ton - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:[0,1]

Given the total number of courses and a list of prerequisitepairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:

1. The input prerequisites is a graph represented by a list of edges , not adjacency matrices. Read more about how a graph is represented .
2. You may assume that there are no duplicate edges in the input prerequisites.

tag: topological sort

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0) return true;

        Map<Integer, Integer> inDegree = new HashMap<>();
        Map<Integer, Set<Integer>> path = new HashMap<>();
        for (int i = 0; i < numCourses; i++){
            inDegree.put(i, 0);
            path.put(i, new HashSet<>());
        }

        // 1. construct
        for (int[] req : prerequisites){
            int target = req[0];
            int preq = req[1];

            inDegree.put(target, inDegree.get(target) + 1);
            path.get(preq).add(target);
        }

        Queue<Integer> q = new LinkedList<>();
        // 2. collect
        for (int key : inDegree.keySet()){
            if (inDegree.get(key) == 0) q.offer(key);
        }

        int ans = 0;
        // 3. bfs
        while (!q.isEmpty()){
            int cur = q.poll();
            ans++;

            for (int neighbor : path.get(cur)){
                inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                if (inDegree.get(neighbor) == 0){
                    q.offer(neighbor);
                }
            }
        }

        return ans == numCourses;
    }
}