Module: Search in depth. DFS


Problem

7 /12


Topological sort

Theory Click to read/hide

The algorithm can be described as follows:
Given a directed graph with n vertices and m edges. It is required to renumber its vertices in such a way that each edge leads from a vertex with a lower number to a vertex with a higher one.
In other words, it is required to find a permutation of vertices (topological order) corresponding to the order given by all the edges of the graph.
We will use depth-first search (dfs(v))
If we add our vertex to the beginning of a list at the time of exit from \(dfs(v)\) , then in the end in this list you get a topological sort.
Thus, the desired topological sort — this is sorted in descending order of exit times.

Problem

Given a directed unweighted graph. It is necessary to sort it topologically.

Input: The first line contains two natural numbers n and m (1≤n≤105, 1≤m≤10< sup>5) — the number of vertices and edges in the graph, respectively. Next m lines list the edges of the graph. Each edge is given by a pair of numbers — the numbers of the start and end vertices, respectively.
 
Output: Print any topological sort of the graph as a sequence of vertex numbers. If the graph cannot be topologically sorted, print −1.
The first line contains the number of vertices N and edges M. 

Examples
# Input Output
1 4 4
14
4 3
4 2
3 2		 1 4 3 2

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!