Challenge 10: Topological Sorting of a Graph

Given a graph, perform topological sorting of 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 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}\{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 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 

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