Module: Suche in die Tiefe. DFS


Problem

7 /12


Topologische Sortierung

Theory Click to read/hide

Der Algorithmus kann wie folgt beschrieben werden:
Dun ist eine Zielzahl mit n Tops und m Rippen. Es ist notwendig, sein Oberteil umzunummerieren, so dass jede Rippe von oben mit einer geringeren Anzahl nach oben mit einer größeren Anzahl angetrieben wird.
Mit anderen Worten, es besteht die Notwendigkeit, nach der von allen Zählrippen festgelegten Reihenfolge nach oben (topologische Reihenfolge) zurückzukehren.
Wir verwenden Bypass in der Tiefe (dfs(v))
Wenn wir hier verschwinden.- Ja.Hinzufügen unserer Spitze zu Beginn einer Liste, es wird schließlich eine Topologie Sortierung sein.
So Der Antrag auf Topologie ist eine Sortierung, um die Zeit der Ausfahrt zu verlieren.

Problem

Ein orientierter, ungewichteter Graph ist gegeben.Es ist notwendig, es topologisch zu sortieren.

Eingabe: Die erste Zeile enthält zwei natürliche Zahlen n und m (1≤n≤105, 1≤m≤105) — die Anzahl der Scheitelpunkte und Kanten im Diagramm. Im Folgenden werden die Kanten des Diagramms in den m-Zeilen aufgelistet. Jede Kante wird durch ein Zahlenpaar mit den Anfangs- und Endpunktnummern angegeben.
 
Ausgabe: Gibt eine beliebige topologische Sortierung des Graphen als Folge von Scheitelpunktnummern aus. Wenn das Diagramm nicht topologisch sortiert werden kann, muss −1 ausgegeben werden.
In der ersten Zeile wird die Anzahl der Scheitelpunkte N und der Kanten M angegeben. 

Beispiele
№ Eingabe Ausgabe
1 4 4
1 4
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!