Challenge 10: Topological Sorting of a Graph

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 $u$ to $v$ if a task $u$ must be completed before a task $y$ can be started.

Find an order of the tasks(graph) in such a way that each task can be performed in the right order.

This problem can be solved if we find the topological sorting of the graph. A topological sort gives an order in which to perform the jobs.

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

Implement a function which takes a Directed Acyclic Graph (DAG) and computes its topological sorting.

Input

A Directed Acyclic Graph.

Output

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