207. Course Schedule
Contents
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
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
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
4
[[2,0],[1,0],[3,1],[3,2],[1,3]]
Output: falseConstraints
- 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
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
}