leetcode 207. 课程表

题解

拓扑排序,找出入度为0的点,然后邻接点的入度各自减1(PS:有向无环图才存在拓扑排序)

示例代码(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
func canFinish(numCourses int, prerequisites [][]int) bool {
graph := make([][]int, numCourses)
indegree := make([]int, numCourses)
for _, v := range prerequisites {
indegree[v[0]]++
graph[v[1]] = append(graph[v[1]], v[0])
}
for {
flag := true
for _, v := range indegree {
if v != -1 {
flag = false
}
}
if flag {
return true
}
flag = true
for i, v := range indegree {
if v == 0 {
flag = false
for _, v1 := range graph[i] {
indegree[v1]--
}
indegree[i]--
break
}
}
if flag {
return false
}
}
return true
}