package Graph
// 时间复杂度: O(n + m), 空间复杂度: O(n + m)
// n为点的数量, m为边的数量
func canFinish(numCourses int, prerequisites [][]int) bool {
graph := make([][]int, numCourses)
inDegree := make([]int, numCourses)
for _, prerequisite := range prerequisites {
from, to := prerequisite[1], prerequisite[0]
graph[from] = append(graph[from], to)
inDegree[to]++
}
queue := new(Queue[int])
for i := 0; i < numCourses; i++ {
if inDegree[i] == 0 {
queue.Enqueue(i)
}
}
for !queue.IsEmpty() {
cur := queue.Dequeue()
for _, next := range graph[cur] {
inDegree[next]--
if inDegree[next] == 0 {
queue.Enqueue(next)
}
}
}
for i := 0; i < numCourses; i++ {
if inDegree[i] != 0 {
return false
}
}
return true
}