54 lines
957 B
Go
54 lines
957 B
Go
package courseschedule
|
|
|
|
func visit(prereqs map[int][]int, temporary map[int]bool, permanent map[int]bool, class int) bool {
|
|
if temporary[class] {
|
|
return false
|
|
}
|
|
if permanent[class] {
|
|
return true
|
|
}
|
|
|
|
if _, ok := prereqs[class]; !ok {
|
|
return true
|
|
}
|
|
|
|
temporary[class] = true
|
|
|
|
for _, p := range prereqs[class] {
|
|
if !visit(prereqs, temporary, permanent, p) {
|
|
return false
|
|
}
|
|
}
|
|
|
|
permanent[class] = true
|
|
temporary[class] = false
|
|
|
|
return true
|
|
}
|
|
|
|
func canFinish(numCourses int, prerequisites [][]int) bool {
|
|
prereqs := map[int][]int{}
|
|
for _, p := range prerequisites {
|
|
class, prerequisite := p[0], p[1]
|
|
|
|
if _, ok := prereqs[class]; !ok {
|
|
prereqs[class] = []int{}
|
|
}
|
|
|
|
prereqs[class] = append(prereqs[class], prerequisite)
|
|
}
|
|
|
|
temporary, permanent := map[int]bool{}, map[int]bool{}
|
|
for c := range prereqs {
|
|
if permanent[c] {
|
|
continue
|
|
}
|
|
|
|
if !visit(prereqs, temporary, permanent, c) {
|
|
return false
|
|
}
|
|
}
|
|
|
|
return true
|
|
}
|