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. 1.
    The input prerequisites is a graph represented by a list of edges , not adjacency matrices.
  2. 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)