← 返回 amazon 的题目列表Course Schedule Conflict Check and Ordering (Topological Sort)
类型：online_judge
You need to schedule n courses labeled 0..n-1. Each prerequisite pair (a, b) means to take course a you must first take course b (directed edge b -> a).
Tasks:
Detect conflicts (cycles). If a cycle exists, print IMPOSSIBLE.
Otherwise, print any valid course order (a topological ordering), space-separated.
Input (stdin)
First line: n m (#courses, #prerequisites)
Next m lines: a b
Output (stdout)
If a cycle exists: IMPOSSIBLE
Else: one line with n integers representing a topological order.
Constraints
1 <= n <= 2*10^5
0 <= m <= 2*10^5
0 <= a,b < n
Example Input:
4 3
1 0
2 0
3 1
Output (one possible):
0 2 1 3
Example
Input
4 3
1 0
2 0
3 1
Output
0 2 1 3