{% tabs %} {% tab title="Go" %}
type queue struct {
course int
}
func findOrder(numCourses int, prerequisites [][]int) []int {
var ans = make([]int,0) // 空list
if len(prerequisites)==0{
for i:=0;i< numCourses;i++ {
ans = append(ans,i)
}
return ans
}
fmt.Println(ans)
var q []queue
var indegree = make([]int, numCourses)
var courses = make(map[int][]int)
for _,v := range prerequisites {
indegree[v[0]]++
courses[v[1]] = append(courses[v[1]],v[0])
}
for i := 0; i < numCourses; i++{
if indegree[i] == 0{
q = append(q,queue{i})
}
}
for len(q)!=0 {
node := q[0]
ans = append(ans,node.course)
q = q[1:]
for _,v := range courses[node.course]{
indegree[v]--
if indegree[v] == 0 {
q = append(q,queue{v})
}
}
}
if len(ans) == numCourses{
return ans
} else {
return make([]int, 0)
}
}
{% endtab %}
{% tab title="Python" %}
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
if not prerequisites:
return list(range(numCourses))
from collections import deque,defaultdict
course = defaultdict(list)
indegree = defaultdict(int)
ans = []
for cour,pres in prerequisites:
course[pres].append(cour)
indegree[cour] += 1
q = deque()
for i in range(numCourses):
if indegree[i] == 0:
q.append(i)
while q:
node = q.popleft()
ans.append(node)
for next_course in course[node]:
indegree[next_course] -= 1 # 更新 预修list
if indegree[next_course] == 0 :
q.append(next_course)
return ans if len(ans)== numCourses else [] # 没学完就是没用
{% endtab %} {% endtabs %}