← 返回 snowflake 的题目列表Topological Sort for Course Schedule with Test Cases
类型：online_judge
Problem: Course Schedule (Return a Valid Order)
Given an integer numCourses (courses labeled 0..numCourses-1) and a list prerequisites where prerequisites[i] = [a, b] means you must take course b before course a.
Return any valid ordering of courses of length numCourses. If it is impossible (the directed graph has a cycle), return an empty array.
Input Format
Line 1: integer numCourses
Line 2: integer m (# of prerequisite pairs)
Next m lines: two integers a b meaning b -> a
Output Format
If possible: print one line with numCourses integers (a valid order)
Otherwise: print an empty line (or [] if explicitly specified)
Constraints
1 <= numCourses <= 2 * 10^5
0 <= m <= 2 * 10^5
0 <= a, b < numCourses
Requirements
O(numCourses + m) time, O(numCourses + m) space
Example
Input:
4
4
1 0
2 0
3 1
3 2
Output (any valid one):
0 1 2 3
Example
Input
4
4
1 0
2 0
3 1
3 2
Output
0 1 2 3