← 返回 netflix 的题目列表Topological Sort (Directed Graph Ordering)
类型:online_judge
Problem: Topological Sort (Directed Graph Ordering)
Given a directed graph with n nodes labeled 0..n-1, and a list of directed edges edges, where each edge (u, v) means you must finish/visit u before v.
Return any valid topological ordering (an array/list of length n) such that for every edge (u, v), u appears before v.
If the graph contains a cycle and no topological ordering exists, return an empty list.
Input (common interview conventions)
n: number of nodes
edges: list of edges, each as two integers u v
Output
Print the ordering space-separated, or print an empty line/empty array if impossible.
Constraints
1 <= n <= 2 * 10^5
0 <= len(edges) <= 2 * 10^5
Example
Input: n = 4, edges = [(1,0),(2,0),(3,1),(3,2)]
Possible output: 3 1 2 0
(Any valid ordering is acceptable.)
Example
Input
4 4
1 0
2 0
3 1
3 2
Output
3 1 2 0
(或任意合法拓扑序)