Topological Sorting
Angenommen, wir haben einen gerichteten Graphen mit
v Knoten und e Kanten und möchten die Knoten in einer bestimmten Reihenfolge anordnen. Existiert eine Kante von v1 nach v2, dann sollte v1 in der Knotenliste vor v2 stehen. Nach dem Sortieren der Knoten wird also jede Kante von einem Knoten mit einem kleineren Index zu einem Knoten mit einem größeren Index verlaufen.🤔
Bedenke, dass es verschiedene mögliche topologische Sortierungen geben kann.
Enthält der Graph jedoch Zyklen, so existiert keine gültige topologische Sortierung.
Die Implementierung des Algorithmus kann mithilfe einer Tiefensuche (DFS) erfolgen, wobei wir von jedem noch nicht besuchten Knoten aus starten. In jeder Iteration rufen wir zunächst rekursiv DFS für alle direkten Nachfolger des aktuellen Knotens auf und fügen erst danach den aktuellen Knoten der Ergebnisliste hinzu. Dadurch stellen wir sicher, dass der Ausgangsknoten später erscheint als alle Knoten, die von ihm aus erreichbar sind. Am Ende des Algorithmus kehren wir die Reihenfolge in der Ergebnisliste um:
used = [False] * n # bereits besuchte Knoten
order = [] # topologische Reihenfolge
def dfs(v): # Tiefensuche (DFS)
used[v] = True # markiere den Knoten als besucht
for to in g[v]: # für jeden an v angrenzenden Knoten to
if not used[to]: # falls to noch nicht besucht wurde
dfs(to) # führe eine Tiefensuche von to aus
order.append(v) # füge v der topologischen Reihenfolge hinzu
for i in range(n): # für jeden Knoten
if not used[i]: # falls dieser Knoten noch nicht besucht ist
dfs(i) # führe eine Tiefensuche von diesem Knoten aus
print(*order[::-1]) # gib die topologische Reihenfolge ausChallenge: Organize the Course Schedule
Du hast
n Kurse, die du belegen möchtest, und insgesamt p Voraussetzungen. Jede Voraussetzung besteht aus einem Paar und bedeutet, dass du den Kurs vor besuchen musst (wenn das Paar zum Beispiel 1, 2 ist, musst du Kurs 2 vor Kurs 1 absolvieren).Es muss überprüft werden, ob du alle Kurse erfolgreich abschließen kannst.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n und p (1 ≤ n, p ≤ 10 000).Die folgenden
p Zeilen enthalten jeweils ein Paar aus zwei ganzen Zahlen (1 ≤ ≤ n).Ausgabe
Das Programm soll
Yes ausgeben, wenn es möglich ist, alle Kurse zu absolvieren, und ansonsten No.Beispiele
Eingabe | Ausgabe |
2 1
2 1 | Yes |
2 2
2 1
1 2 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB