Topological Sort Algorithm
Topological Sort DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Topological Sorting in Directed Acyclic Graphs (DAG), Graph, Directed Graph, Directed Acyclic Graph, Topological Sorting, Adjacency List, Graph Traversal, Depth-First Search, Stack, Time Complexity, Space Complexity, topological sort, visited tracking, graph components, dfs, stack, graph properties, cycle detection, Directed Acyclic Graph (DAG), Topological Sort, Connected Components.
Problem Statement: Given a Directed Acyclic Graph (DAG) with V vertices and E edges, find any valid topological sorting of the graph. In a topological sort, for every directed edge u v, vertex u must appear before vertex v in the ordering. Input Format: 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, indicating a directed edge from u to v. (Vertices are 0 indexed). Output Format: Print the vertices in a single line, space separated, representing one valid topological sorting of the graph. Constraints: 1 <= V <= 10^5 0 <= E <= 2 10^5 0 <= u, v < V The graph is guaranteed to be a Directed Acyclic Graph. Example 1: Input: 6 6 5 0 4 0 5 2 2 3 3 1 4 1 Output: 5 4 2 3 1 0 Explanation: The output is one valid topological sorting. For instance, according to edge 5 0, node 5 must appear before node 0. All such conditions are satisfied. Example 2: Input: 4 3 1 0 2 0 3 0 Output: 3 2 1 0 Explanation: This is one valid topological sorting. For example, for edge 1 0, node 1 must appear before node 0.