Topological Sort — Kahn Algorithm
Practice this coding question on Coding Gurukul.
Problem statement
Given a directed graph, print its lexicographically smallest topological ordering using Kahn’s algorithm. An edge u→v means u must appear before v. When several vertices have indegree 0, choose the smallest numbered one using a min heap. If the graph contains a cycle, print CYCLE only. Otherwise, include every vertex, even isolated ones. Count repeated edges separately when updating indegrees. Target O((n+m) log n) time. Worked example Initially 0, 1 and 3 have indegree 0. Choose 0 and then 1. Vertex 2 becomes available before 3 is chosen, giving 0 1 2 3.
Input format
First line: n m. Next m lines: directed dependency u v.
Output format
Print n vertex numbers in order, or CYCLE.
Constraints
1 <= n <= 100000; 0 <= m <= 200000; 0 <= u,v < n.
Sample input
4 2 0 2 1 2
Sample output
0 1 2 3
Sign in to run or submit a solution in C++, Java or Python.