There are a total of n courses 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 prerequisite pairs, is it possible for you to finish all courses?

Have you met this question in a real interview?

Yes

Example

Given n =2, prerequisites =[[1,0]]
Returntrue

Given n =2, prerequisites =[[1,0],[0,1]]
Returnfalse

1. bfs topological sort. so we can have a integer array to remember the number of prerequisite a course need to have, in another word, the number of times the number showing up in 0 position of the prerequisites list. Then, a hashmap to remember the list of courses that have this course as prerequisite. then add those who have 0 prerequisite into the queue and keep reduce the number of times in the countPrerequiste array, if a number is zero, add to the queue. if queue is empty see if the count equals to the number of courses

public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Write your code here
        if (numCourses == 0) {
            return true;
        }

        int[] preCount = new int[numCourses];
        HashMap<Integer, List<Integer>> courseMap = new HashMap<>();

        for (int i = 0; i < numCourses; i++) {
            List<Integer> cur = new ArrayList<>();
            courseMap.put(i, cur);
        }

        for (int i = 0; i < prerequisites.length; i++) {
            preCount[prerequisites[i][0]]++;
            courseMap.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }

        Queue<Integer> queue = new LinkedList<Integer>();

        for (int i = 0; i < numCourses; i++) {
            if (preCount[i] == 0) {
                queue.offer(i);
            }
        }


        int count = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            count++;
            List<Integer> curList = courseMap.get(cur);
            for (int i = 0; i < curList.size(); i++) {
                preCount[curList.get(i)]--;
                if (preCount[curList.get(i)] == 0) {
                    queue.offer(curList.get(i));
                }
            }
        }

        return count == numCourses;
    }
}