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.