Module: Cerca in profondità. DFS


Problem

7 /12


Ordinamento topologico

Theory Click to read/hide

L'algoritmo può essere descritto come segue:
Dato un grafo orientato con n vertici e m archi. È necessario rinumerare i suoi vertici in modo tale che ogni bordo conduca da un vertice con un numero inferiore a un vertice con uno più alto.
In altre parole, è necessario trovare una permutazione di vertici (ordine topologico) corrispondente all'ordine dato da tutti gli spigoli del grafo.
Useremo la ricerca in profondità (dfs(v))
Se aggiungiamo il nostro vertice all'inizio di una lista al momento dell'uscita da \(dfs(v)\) , allora alla fine in questo elenco ottieni un ordinamento topologico.
Pertanto, l'ordinamento topologico desiderato — questo è ordinato in ordine decrescente di orari di uscita.

Problem

Dato un grafico diretto non pesato. È necessario ordinarlo topologicamente.

Input: La prima riga contiene due numeri naturali n e m (1≤n≤105, 1≤m≤10< sup >5) — il numero di vertici e spigoli nel grafico, rispettivamente. Le m righe successive elencano i bordi del grafico. Ogni spigolo è dato da una coppia di numeri — i numeri dei vertici iniziale e finale, rispettivamente.
 
Output: Stampa qualsiasi ordinamento topologico del grafico come una sequenza di numeri di vertici. Se il grafico non può essere ordinato topologicamente, stampa −1.
La prima riga contiene il numero di vertici N e spigoli M. 

Esempi
# Input Uscita
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!