210.课程表2

leetcode

建立前序后序邻接表，找到入度为零的节点，然后维护邻接表。

最后路径长度等于课程总数则表示可以学完所有课程。

时间复杂度：O(n + m)
空间复杂度：O(n + m)

func findOrder(numCourses int, prerequisites [][]int) []int {
	result := []int{}
	pre := make(map[int][]int)
	post := make(map[int][]int)

	for _, req := range prerequisites {
		x := req[0]
		y := req[1]
		pre[x] = append(pre[x], y)
		post[y] = append(post[y], x)
	}

	// fmt.Printf("pre: %v\n", pre)
	// fmt.Printf("post: %v\n", post)

	queue := []int{}

	for i := 0; i < numCourses; i++ {
		if _, ok := pre[i]; !ok {
			queue = append(queue, i)
		}
	}

	for len(queue) > 0 {
		cur := queue[0]
		result = append(result, cur)
		// fmt.Printf("queue: %v\n", queue)
		queue = queue[1:]
		for _, p := range post[cur] {
			for i, q := range pre[p] {
				if q == cur {
					pre[p] = append(pre[p][:i], pre[p][i+1:]...)
					if len(pre[p]) == 0 {
						queue = append(queue, p)
					}
					break
				}
			}
		}

	}

	if len(result) != numCourses {
		return []int{}
	}

	return result
}