Topological Sort
Mediumjavapythonccppjavascript
Given a directed acyclic graph, return the lexicographically smallest topological ordering of its vertices — an ordering in which, for every directed edge u -> v, u comes before v, and among all such orderings the one that is smallest when compared position by position.
Input Format
The first line contains two integers V and E. Each of the next E lines contains a directed edge u v.
Output Format
Print the lexicographically smallest topological ordering, vertices separated by single spaces.
Example 1
Input
4 4 0 1 0 2 1 3 2 3
Output
0 1 2 3
Explanation: 0 comes before 1 and 2, and both come before 3; picking the smallest available vertex each step gives this order.
- 1 <= V <= 100000
- 0 <= E <= 200000
- The graph is acyclic.
- 0 <= u, v < V
Submit an attempt to unlock the solution. (Sign in first.)
Related Problems
- Detect Cycle in Undirected GraphMedium · java, python, c, cpp, javascriptSolve Problem
- Detect Cycle in Directed GraphMedium · java, python, c, cpp, javascriptSolve Problem
- Shortest Path in Unweighted GraphMedium · java, python, c, cpp, javascriptSolve Problem