Problem
There are a total of numCourses courses you have to take, labeled from 0 to numCourses-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 1
1
2
3
4
|
Input: numCourses = 2, prerequisites = [[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.
|
example 2
1
2
3
4
5
|
Input: numCourses = 2, prerequisites = [[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.
|
example 3
1
2
3
4
|
4
[[2,0],[1,0],[3,1],[3,2],[1,3]]
Output: false
|
Constraints
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
- 1 <=
numCourses <= 10^5
Solution
DFS
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
|
func canFinish(numCourses int, prerequisites [][]int) bool {
m := make(map[int][]int, numCourses+1)
for idx:= range prerequisites {
if _, ok := m[prerequisites[idx][0]]; !ok {
m[prerequisites[idx][0]] = make([]int,0)
}
m[prerequisites[idx][0]] = append(m[prerequisites[idx][0]], prerequisites[idx][1])
}
for idx := range m {
if !helper(m,idx, map[int]int{}) {
return false
}
}
return true
}
func helper( m map[int][]int, idx int, v map[int]int) bool {
if _, ok := v[idx]; ok {
return false
}
v[idx] = 1
for jdx := range m[idx] {
if !helper(m, m[idx][jdx], v){
return false
}
delete(v, m[idx][jdx])
}
return true
}
|