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