-
Notifications
You must be signed in to change notification settings - Fork 0
/
courseSchedule.go
75 lines (67 loc) · 1.8 KB
/
courseSchedule.go
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package _021_05
// Course Schedule
// leetcode: https://leetcode-cn.com/problems/course-schedule/
// There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1.
// You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
// For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
// Return true if you can finish all courses. Otherwise, return false.
// 拓扑排列 DFS
func CourseSchedule(numCourses int, prerequisites [][]int) bool {
edges := make([][]int, numCourses)
// searched 0 => 未搜索 1 => 搜索中 2 => 已搜索
searched := make([]int, numCourses)
valid := true
var dfs func(c int)
dfs = func(c int) {
searched[c] = 1
for _, v := range edges[c] {
if searched[v] == 0 {
dfs(v)
if !valid {
return
}
}else if searched[v] == 1 {
valid = false
return
}
}
searched[c] = 2
}
for _, prerequisite := range prerequisites {
edges[prerequisite[1]] = append(edges[prerequisite[1]], prerequisite[0])
}
for i := 0; i < numCourses && valid; i++ {
if searched[i] == 0 {
dfs(i)
}
}
return valid
}
// 拓扑排列 BFS
func CourseSchedule2(numCourses int, prerequisites [][]int) bool {
edges := make([][]int, numCourses)
indegree := make([]int, numCourses)
result := 0
for _, prerequisite := range prerequisites {
edges[prerequisite[1]] = append(edges[prerequisite[1]], prerequisite[0])
indegree[prerequisite[0]]++
}
q := []int{}
for i := 0; i < numCourses; i++ {
if indegree[i] == 0 {
q = append(q, i)
}
}
for len(q) > 0 {
c := q[0]
q = q[1:]
result++
for _, v := range edges[c] {
indegree[v]--
if indegree[v] == 0 {
q = append(q, v)
}
}
}
return result == numCourses
}