##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
4 4 1 2 1 3 2 4 3 4
1 2 3 4
3 3 1 2 2 3 3 1
Input: Graph with cycle 1→2→3→1
Kahn's algorithm cannot process all vertices (cycle detected).
Answer: -1
-1
5 4 5 1 5 2 1 3 2 3
Input: DAG with 5 vertices
Vertex 4 has in-degree 0. After processing, lexicographically smallest order.
Answer: 4 5 1 2 3
4 5 1 2 3
Given a directed acyclic graph (DAG) with vertices and edges, find a topological ordering of the vertices using Kahn's algorithm (BFS-based).
A topological ordering is a linear ordering of vertices such that for every directed edge , vertex comes before .
If multiple valid orderings exist, output the lexicographically smallest one.
If the graph contains a cycle, output -1.
Each edge goes from to .
A valid topological ordering (lexicographically smallest), or if a cycle exists.
Input: DAG with edges 1→2, 1→3, 2→4, 3→4
Kahn's algorithm:
Answer: 1 2 3 4
