Description

here are a total of n courses you have to take, labeled from 0 to n - 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?

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.

Hint

Train of Thought

BFS topological sort

Code

//recommend this solution
//another solution using adjacent list
public boolean canFinish(int numCourses, int[][] prerequisites){
    int[] incomingEdges = new int[numCourses];
    List<Integer>[] goCourses = new List[numCourses];
    for(int i=0;i<goCourses.length;i++){
        goCourses[i] = new LinkedList<Integer>();
    }
    for(int[] pair: prerequisites){
        incomingEdges[pair[0]]++;
        goCourses[pair[1]].add(pair[0]);
    }
    Queue<Integer> queue = new LinkedList<Integer>();
    for(int i=0;i<incomingEdges.length;i++){
        if(incomingEdges[i]==0){
            queue.add(i);
        }
    }
    int edgeCnt = prerequisites.length;
    while(!queue.isEmpty()){
        int cur = queue.poll();
        for(int goCrs: goCourses[cur]){
             edgeCnt--;
             if(--incomingEdges[goCrs]==0)
                queue.add(goCrs);
        }
    }
    return edgeCnt==0;
}


//this passed solution why using pair[1] as indegree
public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] indegree = new int[numCourses];
    Queue<Integer> queue = new LinkedList<Integer>();
    for(int[] pair:prerequisites){
        indegree[pair[1]]++;
    }
    for(int i=0;i<indegree.length;i++){
        if(indegree[i]==0){
            queue.add(i);
        }
    }
    int select = 0;
    while(!queue.isEmpty()){
        numCourses--;
        int course = queue.poll();
        for(int[] pair:prerequisites){
            if(pair[0]==course){
                indegree[pair[1]]--;
                if(indegree[pair[1]]==0){
                    queue.add(pair[1]);
                }
            }
        }
    }
    return numCourses==0;
}

Complexity