Kahn's Algorithm

Topological Sort of a Directed Acyclic Graph Problem Statement Given a Directed Acyclic Graph (DAG) with V vertices and E edges, find any valid topological sorting of that graph. Note: In a topological sorting, if there is a directed edge from node u to node v (i.e., u v), then u must appear before v in the sorted order. Input Specification The first line contains two integers V and E, representing the number of vertices and edges, respectively. The next E lines each contain two integers u and v, denoting a directed edge from u to v. Output Specification Print a space separated list of integers representing any valid topological sorting of the graph. Constraints Implicitly, V and E are non negative, and graph nodes are typically 0 indexed or 1 indexed. The examples use 0 indexed nodes. Example 1 Input Format: Output Format: Explanation: A graph may have multiple topological sortings. The output is one such valid ordering. The necessary conditions for this ordering are satisfied: For edge 5 0, node 5 appears before node 0. For edge 4 0, node 4 appears before node 0. For edge 5 2, node 5 appears before node 2. For edge 2 3, node 2 appears before node 3. For edge 3 1, node 3 appears before node 1. For edge 4 1, node 4 appears before node 1. Other valid topological sortings for this graph include 4 5 2 3 1 0 and 4 5 0 2 3 1. Example 2 Input Format: Output Format: Explanation: The necessary conditions for this ordering are satisfied: For edge 1 0, node 1 appears before node 0. For edge 2 0, node 2 appears before node 0. For edge 3 0, node 3 appears before node 0. Another valid topological sorting for this graph is 2 3 1 0.