mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-04 16:12:47 +08:00
31 lines
590 B
Go
31 lines
590 B
Go
package leetcode
|
|
|
|
func findOrder(numCourses int, prerequisites [][]int) []int {
|
|
in := make([]int, numCourses)
|
|
frees := make([][]int, numCourses)
|
|
next := make([]int, 0, numCourses)
|
|
for _, v := range prerequisites {
|
|
in[v[0]]++
|
|
frees[v[1]] = append(frees[v[1]], v[0])
|
|
}
|
|
for i := 0; i < numCourses; i++ {
|
|
if in[i] == 0 {
|
|
next = append(next, i)
|
|
}
|
|
}
|
|
for i := 0; i != len(next); i++ {
|
|
c := next[i]
|
|
v := frees[c]
|
|
for _, vv := range v {
|
|
in[vv]--
|
|
if in[vv] == 0 {
|
|
next = append(next, vv)
|
|
}
|
|
}
|
|
}
|
|
if len(next) == numCourses {
|
|
return next
|
|
}
|
|
return []int{}
|
|
}
|