← 返回 airbnb 的题目列表Dependency Resolution / Build Order
类型：online_judge
Problem: Dependency Resolution (Build Order)
You are given a set of packages/tasks and their dependencies. Compute a valid installation/execution order.
Each dependency is a pair (A, B) meaning: to do A, you must do B first (i.e., edge B -> A).
If there is a cycle and it is impossible to complete all tasks, return an empty result.
Input
Line 1: two integers n m
n tasks labeled 0..n-1
m dependency pairs
Next m lines: two integers a b meaning a depends on b.
Output
If possible: print one line with n integers representing one valid order.
If impossible (cycle): print an empty line (or IMPOSSIBLE depending on interviewer preference).
Constraints
1 <= n <= 2e5
0 <= m <= 2e5
Task IDs are in [0, n-1]
Sample Tests (stdin/stdout)
input:
4 3
1 0
2 0
3 1
output:
0 2 1 3
input:
2 2
0 1
1 0
output:
input:
3 0
output:
0 1 2
input:
5 5
1 0
2 1
3 2
4 3
2 0
output:
0 1 2 3 4
input:
6 6
1 0
2 0
3 1
3 2
4 3
5 4
output:
0 2 1 3 4 5
Example
Input
4 3
1 0
2 0
3 1
Output
0 2 1 3