Challenge: Topological Sorting of a Graph

Given a graph, topologically sort it.

Problem statement

You have been given the task to schedule tasks. The tasks are represented by vertices of a graph, and there is an edge from uu to vv if a task uu must be completed before a task yy can be started.

Find the order of the tasks(graph) so that each task can be performed in the right order.

This problem can be solved by finding the topological sorting of the graph. A topological sort gives the order in which to perform the jobs.

Topological sorting for a Directed Acyclic Graph (DAG) is a linear ordering of vertices, such that for every directed edge {u,v}\{u,v\}, vertex uu comes before vv in the ordering. Topological sorting for a graph is not possible if the graph is not a DAG.

Implement a function that takes a directed acyclic graph (DAG) and computes its topological sorting.

Input

The input is a directed acyclic graph.

Output

The output is the topological sorting of the graph.

Sample input

graph = {
    5 -> 2
    5 -> 0
    4 -> 0
    4 -> 1
    2 -> 3
    3 -> 1
}

Sample output

5 4 2 3 1 0 

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.