← 返回 bytedance 的题目列表Print Execution Order in a DAG and Detect Cycles
类型：online_judge
Problem: Print Execution Order in a DAG and Detect Cycles
You are given n tasks numbered from 0 to n - 1, and m dependency relations. Each dependency is a directed edge u v, meaning task u must be executed before task v.
Print a valid execution order such that for every dependency u -> v, u appears before v.
If the dependency graph contains a cycle, no valid execution order exists. In that case, print IMPOSSIBLE.
Input Format
n m
u1 v1
u2 v2
...
um vm
n: number of tasks
m: number of dependency relations
Each edge u v means u must be executed before v
Output Format
If a valid execution order exists, print one line containing n integers.
If the graph contains a cycle, print:
IMPOSSIBLE
Constraints
1 <= n <= 2 * 10^5
0 <= m <= 2 * 10^5
0 <= u, v < n
The graph may be disconnected
The graph may contain a cycle
Example 1
Input:
4 4
0 1
0 2
1 3
2 3
Output:
0 1 2 3
Example 2
Input:
3 3
0 1
1 2
2 0
Output:
IMPOSSIBLE
Example
Input
4 4
0 1
0 2
1 3
2 3
Output
0 1 2 3