Strongly Connected Components
Ein gerichteter Graph hat n Knoten, nummeriert von 0 bis n-1, und eine Liste von edges, wobei [from, to] eine Kante vom Knoten from zum Knoten to ist.
Eine stark zusammenhängende Komponente ist eine größtmögliche Gruppe von Knoten, in der jeder Knoten jeden anderen Knoten erreichen kann, indem er Kanten folgt. Jeder Knoten gehört genau einer Komponente an, und ein Knoten, der auf keinem Zyklus liegt, bildet eine Komponente für sich. Gib die Anzahl der stark zusammenhängenden Komponenten zurück.
Funktion
- ninteger
- die Anzahl der Knoten
- edgesinteger-2d-array
- die gerichteten Kanten, jeweils als [from, to]
- Gibt zurückinteger
- die Anzahl der stark zusammenhängenden Komponenten
Einschränkungen
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to]mit0 ≤ from, to < nundfrom ≠ to- Keine Kante kommt zweimal vor.
Beispiele
- Eingabe
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- Ausgabe
- 3
- Erklärung
- Die Knoten 0, 1 und 2 bilden eine Schleife, sodass sie einander erreichen. Die Knoten 3 und 4 zeigen aufeinander. Knoten 5 erreicht 4, aber nichts führt zurück zu 5, daher steht er allein: 3 Komponenten.
- Eingabe
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- Ausgabe
- 4
- Erklärung
- Die Knoten 0 und 1 zeigen aufeinander und bilden eine Komponente. Die Kante von 2 nach 3 verläuft nur in eine Richtung, daher sind 2 und 3 getrennt, und Knoten 4 hat überhaupt keine Kanten: 4 Komponenten.
Weiterführende Frage
Wie wenige Kanten müsstest du hinzufügen, damit der gesamte Graph eine einzige stark zusammenhängende Komponente ist?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Zwei Knoten teilen sich genau dann eine Komponente, wenn jeder den anderen erreichen kann. Eine Suche von jedem Knoten aus kann das überprüfen, durchläuft dabei aber immer wieder dieselben Kanten. Was kann eine einzige Tiefensuche darüber verraten, wo eine Komponente beginnt?
Nummeriere die Knoten in der Reihenfolge, in der die Tiefensuche sie zum ersten Mal erreicht. Verfolge für jeden Knoten außerdem
low: die kleinste Nummer, die er erreichen kann, indem er im Suchbaum nach unten geht und anschließend einer Kante zurück zu einem Knoten folgt, dessen Komponente noch offen ist. Ein Knoten, dessenlowseiner eigenen Nummer entspricht, ist der erste Knoten seiner Komponente.Halte die besuchten Knoten auf einem Stack fest. Wenn die Suche bei einem Knoten endet und
lowgleich seiner eigenen Nummer ist, entferne die Knoten vom Stack bis einschließlich dieses Knotens: Diese Knoten bilden eine Komponente, also zähle sie. Ein Test lässt die Suche 5000 Knoten tief werden. Verwende daher einen eigenen Stack aus (Knoten, nächste Kante)-Frames, statt zu rekursieren.
Lösung
Schrumpft man jede Komponente zu einem Punkt, bilden die Komponenten einen Graphen ohne Zyklen. Die Algorithmen von Kosaraju und Tarjan nutzen das, um jede Komponente in O(n + E) zu finden, wobei E die Anzahl der Kanten ist.
Suche vorwärts und rückwärts von jedem Knoten aus
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Knoten u und v gehören genau dann zur selben Zusammenhangskomponente, wenn jeder den anderen erreichen kann. Suche also für einen Knoten s, der noch keiner Komponente angehört, vorwärts entlang der Kanten und rückwärts entlang der umgekehrten Kanten. Die bei beiden Suchen gefundenen Knoten bilden seine Komponente. Im ersten Beispiel findet die Vorwärtssuche von 0 aus die Knoten 0 bis 4, und die Rückwärtssuche findet 0, 1 und 2. Daher ist {0, 1, 2} eine Komponente.
Für jede Komponente sind zwei Suchen nötig, die sich über den größten Teil des Graphen erstrecken. Bei einer Kette aus 5000 Kanten und 5001 Knoten ist jeder Knoten seine eigene Komponente, und die Suchen besuchen etwa 2.5 × 10^7 Knoten.
Algorithmus
- Erstelle die Listen der ausgehenden und eingehenden Kanten für jeden Knoten.
- Nimm den nächsten Knoten
sohne Komponente und zähle eine neue Komponente. - Markiere, welche Knoten
süber ausgehende Kanten erreicht und welche über eingehende Kanten zusgelangen. - Jeder Knoten, der von beiden Suchen markiert wurde, gehört zur Komponente von
s. Wenn jeder Knoten einer Komponente zugeordnet ist, gib die Anzahl zurück.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
done = [False] * n
# fwd[v] == s: the search forward from s reached v. bwd[v] == s: v reaches s.
fwd = [-1] * n
bwd = [-1] * n
count = 0
for s in range(n):
if done[s]:
continue
count += 1
# Every node s can reach.
fwd[s] = s
reached = [s]
stack = [s]
while stack:
node = stack.pop()
for nxt in out[node]:
if fwd[nxt] != s:
fwd[nxt] = s
reached.append(nxt)
stack.append(nxt)
# Every node that can reach s.
bwd[s] = s
stack = [s]
while stack:
node = stack.pop()
for prev in rev[node]:
if bwd[prev] != s:
bwd[prev] = s
stack.append(prev)
# The nodes found both ways form the component of s.
for v in reached:
if bwd[v] == s:
done[v] = True
return countKosaraju-Algorithmus: zwei Durchläufe
Idee
Im Komponentengraphen ist eine Komponente eine Senke, aus der keine Kante herausführt, und eine Suche, die innerhalb dieser Komponente gestartet wird, findet genau diese Komponente. Der Algorithmus von Kosaraju ordnet die Suchen so an, dass jede sich genau so verhält.
Im ersten Durchlauf werden alle Knoten aufgelistet, sobald ihre Tiefensuche abgeschlossen ist. Im zweiten Durchlauf wird der umgekehrte Graph durchsucht, der dieselben Komponenten hat, und zwar beginnend mit dem Knoten, dessen Suche zuletzt abgeschlossen wurde. Führt eine Kante von Komponente B nach C, wird der letzte Knoten von B nach allen Knoten von C abgeschlossen. Wenn der zweite Durchlauf also C erreicht, ist jede Komponente mit einer Kante nach C bereits zugeordnet, und auf dem umgekehrten Graphen kann die Suche C nicht verlassen.
Im ersten Beispiel werden die Knoten in der Reihenfolge 4, 3, 2, 1, 0, 5 abgeschlossen. Der zweite Durchlauf sammelt {5}, dann {0, 1, 2}, dann {3, 4}.
Algorithmus
- Erstelle die Listen der ausgehenden und eingehenden Kanten.
- Führe von jedem unbesuchten Knoten aus eine iterative Tiefensuche durch und füge jeden Knoten zu
orderhinzu, wenn die Suche für ihn abgeschlossen ist. - Durchlaufe
ordervom Ende her. Zähle für jeden Knoten ohne Komponente eine neue Komponente und suche von ihm aus entlang der eingehenden Kanten. Weise jedem nicht zugewiesenen Knoten, den du erreichst, diese Komponente zu. Gib die Anzahl zurück.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
# Pass 1: depth first search on the graph, listing each node when it finishes.
seen = [False] * n
order = []
for start in range(n):
if seen[start]:
continue
seen[start] = True
# Each frame is [node, next edge to try].
stack = [[start, 0]]
while stack:
frame = stack[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if not seen[nxt]:
seen[nxt] = True
stack.append([nxt, 0])
else:
stack.pop()
order.append(node)
# Pass 2: on the reversed graph, start from the last node to finish.
# Each search collects exactly one component.
done = [False] * n
count = 0
for start in reversed(order):
if done[start]:
continue
count += 1
done[start] = True
stack = [start]
while stack:
node = stack.pop()
for prev in rev[node]:
if not done[prev]:
done[prev] = True
stack.append(prev)
return countTarjans Algorithmus: ein Durchlauf mit Low-Werten
Idee
Führe eine Tiefensuche durch und nummeriere jeden Knoten in der Reihenfolge, in der du ihn erreichst: seinen index. Behalte einen Stapel besuchter Knoten, deren Komponente noch offen ist, sowie einen Wert low: den kleinsten Index, den ein Knoten erreicht, indem er im Suchbaum nach unten geht und dann über eine Kante zu einem Knoten auf diesem Stapel zurückkehrt.
Wenn ein Knoten mit einem low-Wert kleiner als seinem index fertig ist, führt etwas unterhalb von ihm zurück zu einem früher erreichten offenen Knoten, daher bleibt er auf dem Stapel. Sind die Werte gleich, ist der Knoten der erste, den die Suche in seiner Komponente erreicht hat: Entferne die Knoten vom Stapel bis einschließlich dieses Knotens und zähle eine Komponente. Eine Kante zu einem bereits entfernten Knoten führt in eine abgeschlossene Komponente, die nicht zurückreichen kann, und wird daher ignoriert.
Im ersten Beispiel entfernt 3 die Knoten {4, 3} und 0 die Knoten {2, 1, 0} vom Stapel. Die Kante von Knoten 5 führt zum bereits entfernten Knoten 4, daher wird 5 allein vom Stapel entfernt.
Algorithmus
- Gib jedem noch nicht besuchten Knoten den nächsten Index, setze
lowauf denselben Wert, lege ihn auf den Knotenstapel und lege den Frame (node, first edge) auf den Stapel. - Hat der Knoten im obersten Frame noch eine Kante, folge ihr: Ein nicht besuchtes Ziel erhält einen Index und einen Frame, und bei einem Ziel auf dem Knotenstapel wird
low[node]auf dessen Index gesetzt. - Andernfalls entferne den Frame und setze
lowdes Elternknotens auflow[node]. Wennlow[node]gleichindex[node]ist, entferne Knoten vom Knotenstapel bis einschließlich des Knotens und zähle eine Komponente.
def countSCC(n, edges):
out = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
index = [-1] * n # discovery time, -1 while unvisited
low = [0] * n # earliest discovery time the node can reach and still return from
on_stack = [False] * n
stack = [] # visited nodes whose component is still open
time = 0
count = 0
for start in range(n):
if index[start] != -1:
continue
index[start] = low[start] = time
time += 1
stack.append(start)
on_stack[start] = True
# The depth first search keeps its own call stack: [node, next edge to try].
calls = [[start, 0]]
while calls:
frame = calls[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if index[nxt] == -1:
index[nxt] = low[nxt] = time
time += 1
stack.append(nxt)
on_stack[nxt] = True
calls.append([nxt, 0])
elif on_stack[nxt]:
# An edge back into an open component.
low[node] = min(low[node], index[nxt])
else:
calls.pop()
if calls:
parent = calls[-1][0]
low[parent] = min(low[parent], low[node])
# Nothing below node reaches above it: node closes a component.
if low[node] == index[node]:
count += 1
while True:
w = stack.pop()
on_stack[w] = False
if w == node:
break
return count
Stolperfallen und Grenzfälle
- Knoten ohne Kanten vergessen. Im zweiten Beispiel kommt Knoten 4 in keiner Kante vor und ist trotzdem eine Komponente.
lowüber jeden besuchten Knoten aktualisieren, statt nur über Knoten auf dem Stack. Im ersten Beispiel verhindert die Kante5 → 4dann, dass 5 seine Komponente abschließt.- Die Kanten als bidirektional behandeln. Dadurch werden zusammenhängende Komponenten gezählt: Das erste Beispiel ergäbe 1 statt 3.
- In Python rekursiv aufrufen. Ein Zyklus durch 5000 Knoten verschachtelt 5000 Aufrufe, also fünfmal so viele wie das Standardlimit von 1000. Verwende einen eigenen Stack mit Frames.
- Den zweiten Durchlauf von Kosaraju auf den ursprünglichen Kanten oder in der Reihenfolge ausführen, in der die Knoten zuerst besucht wurden. Beides führt dazu, dass Komponenten zusammengeführt werden, die sich nur in eine Richtung erreichen können.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität beim Finden stark zusammenhängender Komponenten?
O(n + E) Zeit mit dem Algorithmus von Kosaraju oder Tarjan, da jeder Knoten und jede Kante eine konstante Anzahl von Malen verarbeitet wird. Beide benötigen O(n + E) Speicherplatz für die Kantenlisten und die Suchstapel.
Solltest du den Kosaraju- oder den Tarjan-Algorithmus verwenden?
Der Algorithmus von Kosaraju besteht aus zwei einfachen Suchen und ist schwerer falsch zu implementieren. Tarjans Algorithmus benötigt eine Suche und keinen umgekehrten Graphen, dafür aber die low-Verwaltung.
Was ist der Unterschied zwischen stark zusammenhängenden Komponenten und zusammenhängenden Komponenten?
Zusammenhängende Komponenten ignorieren die Richtung der Kanten: Zwei Knoten gehören zusammen, wenn ein Pfad sie verbindet. Bei stark zusammenhängenden Komponenten muss jeder Knoten den anderen erreichen können. Das erste Beispiel ist eine zusammenhängende Komponente, aber es besteht aus drei stark zusammenhängenden Komponenten.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def countSCC(n, edges):
# Schreibe hier den CodeTest #1
Test #2
Argumente
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
Erwartete Ausgabe
3