[LeetCode] Problem 207 - Course Schedule

Posted on | In ,

There 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?

Example

No.1

Input: 2, [[1,0]]

Output: true

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

No.2

Input: 2, [[1,0],[0,1]]

Output: false

Explanation: 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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    List[] adj = new ArrayList[numCourses];
    int count = 0;

    for (int i = 0; i < numCourses; i++)
        adj[i] = new ArrayList<Integer>();

    for (int[] prerequisite : prerequisites) {
        adj[prerequisite[1]].add(prerequisite[0]);
        inDegree[prerequisite[0]]++;
    }

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

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

    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;

        for (int i = 0; i < adj[course].size(); i++) {
            int postrequisite = (int) adj[course].get(i);
            inDegree[postrequisite]--;

            if (inDegree[postrequisite] == 0)
                queue.offer(postrequisite);
        }
    }

    return count == numCourses;
}