package coursescheduleii

// 210. 课程表 II
// https://leetcode-cn.com/problems/course-schedule-ii/

func findOrder(numCourses int, prerequisites [][]int) []int {
	to := make([][]int, numCourses)
	inDeg := make([]int, numCourses)

	for _, p := range prerequisites {
		to[p[1]] = append(to[p[1]], p[0])
		inDeg[p[0]]++
	}
	queue := []int{}
	// 拓扑排序第一步，从入度 = 0 的课开始
	for i := 0; i < numCourses; i++ {
		if inDeg[i] == 0 {
			queue = append(queue, i)
		}
	}
	lessons := []int{}
	for len(queue) > 0 {
		h := queue[0]
		queue = queue[1:]
		lessons = append(lessons, h)
		// 第二步，周围的点入度减一
		for _, t := range to[h] {
			inDeg[t]--
			// 第三步，入度 = 0 ，可以入 queue
			if inDeg[t] == 0 {
				queue = append(queue, t)
			}
		}
	}
	if len(lessons) == numCourses {
		return lessons
	}
	return nil
}