Module: Recherche en profondeur. DFS


Problem

7 /12


Tri topologique

Theory Click to read/hide

L'algorithme peut être décrit comme suit :
Soit un graphe orienté à n sommets et m arêtes. Il est nécessaire de renuméroter ses sommets de manière à ce que chaque arête mène d'un sommet avec un numéro inférieur à un sommet avec un numéro supérieur.
En d'autres termes, il s'agit de trouver une permutation de sommets (ordre topologique) correspondant à l'ordre donné par toutes les arêtes du graphe.
Nous allons utiliser la recherche en profondeur (dfs(v))
Si nous ajoutons notre sommet au début d'une liste au moment de la sortie de \(dfs(v)\) , alors à la fin dans cette liste vous obtenez un tri topologique.
Ainsi, le tri topologique souhaité — ceci est trié par ordre décroissant des heures de sortie.

Problem

Etant donné un graphe orienté non pondéré. Il est nécessaire de le trier topologiquement.

Entrée : La première ligne contient deux nombres naturels n et m (1≤n≤105, 1≤m≤10< sup >5) — le nombre de sommets et d'arêtes dans le graphe, respectivement. Les m lignes suivantes listent les arêtes du graphe. Chaque arête est donnée par une paire de nombres — les numéros des sommets de début et de fin, respectivement.
 
Sortie : Imprime n'importe quel tri topologique du graphe sous la forme d'une séquence de numéros de sommets. Si le graphique ne peut pas être trié topologiquement, imprimez &moins;1.
La première ligne contient le nombre de sommets N et d'arêtes M. 

Exemples
# Entrée Sortie
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!