mirror of https://github.com/doocs/leetcode.git
31 lines
546 B
Go
31 lines
546 B
Go
func findOrder(numCourses int, prerequisites [][]int) []int {
|
|
g := make([][]int, numCourses)
|
|
indeg := make([]int, numCourses)
|
|
for _, p := range prerequisites {
|
|
a, b := p[0], p[1]
|
|
g[b] = append(g[b], a)
|
|
indeg[a]++
|
|
}
|
|
q := []int{}
|
|
for i, x := range indeg {
|
|
if x == 0 {
|
|
q = append(q, i)
|
|
}
|
|
}
|
|
ans := []int{}
|
|
for len(q) > 0 {
|
|
i := q[0]
|
|
q = q[1:]
|
|
ans = append(ans, i)
|
|
for _, j := range g[i] {
|
|
indeg[j]--
|
|
if indeg[j] == 0 {
|
|
q = append(q, j)
|
|
}
|
|
}
|
|
}
|
|
if len(ans) == numCourses {
|
|
return ans
|
|
}
|
|
return []int{}
|
|
} |