207 Course Schedule

Search…
207 Course Schedule
207. Course Schedule
1. Question
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 prerequisite pairs, is it possible for you to finish all courses?
For example:
1
2, [[1,0]]
Copied!
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
1
2, [[1,0],[0,1]]
Copied!
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. 
2.You may assume that there are no duplicate edges in the input prerequisites.
2. Implementation
(1) BFS
1
class Solution {
2
    public boolean canFinish(int numCourses, int[][] prerequisites) {
3
        List<Set<Integer>> adjList = new ArrayList<>();
4
​
5
        for (int i = 0; i < numCourses; i++) {
6
            adjList.add(new HashSet<>());
7
        }
8
​
9
        int[] inDegree = new int[numCourses];
10
​
11
        for (int[] prerequisite : prerequisites) {
12
            adjList.get(prerequisite[0]).add(prerequisite[1]);
13
            ++inDegree[prerequisite[1]];
14
        }
15
​
16
        Queue<Integer> queue = new LinkedList<>();
17
​
18
        for (int i = 0; i < numCourses; i++) {
19
            if (inDegree[i] == 0) {
20
                queue.add(i);
21
            }
22
        }
23
​
24
        int count = 0;
25
​
26
        while (!queue.isEmpty()) {
27
            int course = queue.remove();
28
            ++count;
29
​
30
            for (int nextCourse : adjList.get(course)) {
31
                if (--inDegree[nextCourse] == 0) {
32
                    queue.add(nextCourse);
33
                }
34
            }
35
        }
36
        return count == numCourses;
37
    }
38
}
Copied!
(2) DFS
1
class Solution {
2
    public boolean canFinish(int numCourses, int[][] prerequisites) {
3
        int n = numCourses;
4
​
5
        List<Set<Integer>> adjList = new ArrayList<>();
6
​
7
        for (int i = 0; i < n; i++) {
8
            adjList.add(new HashSet<>());
9
        }
10
​
11
        for (int[] prerequisite : prerequisites) {
12
            adjList.get(prerequisite[1]).add(prerequisite[0]);
13
        }
14
​
15
        boolean[] visited = new boolean[n];
16
        boolean[] onStack = new boolean[n];
17
​
18
        for (int i = 0; i < n; i++) {
19
            if (!visited[i]) {
20
                if (!dfs(i, visited, onStack, adjList)) {
21
                    return false;
22
                }
23
            }
24
        }
25
        return true;
26
    }
27
​
28
    public boolean dfs(int course, boolean[] visited, boolean[] onStack, List<Set<Integer>> adjList) {
29
        if (visited[course]) {
30
            return true;
31
        }
32
​
33
        if (onStack[course]) {
34
            return false;
35
        }
36
​
37
        onStack[course] = true;
38
​
39
        for (int nextCourse : adjList.get(course)) {
40
            if (!dfs(nextCourse, visited, onStack, adjList)) {
41
                return false;
42
            }
43
        }
44
​
45
        visited[course] = true;
46
        onStack[course] = false;
47
        return true;
48
    }
49
}
Copied!
3. Time & Space Complexity
BFS: 时间复杂度O(n)，空间复杂度O(n)
DFS: 时间复杂度O(n)，空间复杂度O(n)
Topological Sort
210 Course Schedule II
Last modified 2yr ago
Copy link
Contents
207. Course Schedule
1. Question
2. Implementation
3. Time & Space Complexity