Strongly Connected Components
Un grafo orientato ha n nodi, numerati da 0 a n-1, e un elenco di edges, dove [from, to] è un arco dal nodo from al nodo to.
Una componente fortemente connessa è il gruppo più grande di nodi in cui ogni nodo può raggiungere tutti gli altri seguendo gli archi. Ogni nodo appartiene esattamente a una componente, e un nodo che non si trova su alcun ciclo forma una componente a sé. Restituisci il numero di componenti fortemente connesse.
Funzione
- ninteger
- il numero di nodi
- edgesinteger-2d-array
- gli archi orientati, ciascuno come [from, to]
- Restituisceinteger
- il numero di componenti fortemente connesse
Vincoli
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to]con0 ≤ from, to < nefrom ≠ to- Nessun arco appare due volte.
Esempi
- Input
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- Output
- 3
- Spiegazione
- I nodi 0, 1 e 2 formano un ciclo, quindi si raggiungono a vicenda. I nodi 3 e 4 puntano l’uno all’altro. Il nodo 5 raggiunge il 4, ma nulla torna al 5, quindi resta isolato: 3 componenti.
- Input
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- Output
- 4
- Spiegazione
- I nodi 0 e 1 puntano l’uno all’altro e formano un componente. L’arco da 2 a 3 va in una sola direzione, quindi 2 e 3 sono separati, e il nodo 4 non ha alcun arco: 4 componenti.
Per approfondire
Quanti archi dovresti aggiungere al minimo per rendere l’intero grafo un’unica componente fortemente connessa?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Due nodi condividono una componente esattamente quando ciascuno può raggiungere l’altro. Una ricerca da ogni nodo può verificarlo, ma percorre gli stessi archi più e più volte. Cosa può dirti una singola ricerca in profondità su dove inizia una componente?
Numera i nodi nell’ordine in cui una ricerca in profondità li raggiunge per la prima volta. Per ogni nodo tieni traccia anche di
low: il numero più piccolo che può raggiungere scendendo nell’albero di ricerca e poi seguendo un arco all’indietro verso un nodo il cui componente è ancora aperto. Un nodo il cuilowè uguale al proprio numero è il primo nodo del suo componente.Mantieni i nodi visitati in uno stack. Quando un nodo termina con
lowuguale al proprio numero, rimuovi nodi dallo stack fino a raggiungere quel nodo: quei nodi formano una componente, quindi contala. Un test porta la ricerca a una profondità di 5000 nodi, quindi usa il tuo stack di frame (nodo, arco successivo) invece di ricorrere.
Soluzione
Riduci ogni componente a un punto e le componenti formano un grafo senza cicli. Gli algoritmi di Kosaraju e Tarjan sfruttano questo per trovare ogni componente in O(n + E), dove E è il numero di archi.
Cerca in avanti e all'indietro da ogni nodo
Corretto, ma non termina sui test più grandi
Intuizione
I nodi u e v condividono una componente esattamente quando ciascuno raggiunge l’altro. Quindi, per un nodo s che non appartiene ancora a nessuna componente, cerca in avanti lungo gli archi e all’indietro lungo gli archi invertiti. I nodi trovati da entrambe le ricerche formano la sua componente. Nel primo esempio, partendo da 0 in avanti si trovano i nodi da 0 a 4, mentre all’indietro si trovano 0, 1 e 2, quindi {0, 1, 2} è una componente.
Ogni componente richiede due ricerche su gran parte del grafo. In una catena di 5000 archi che attraversa 5001 nodi, ogni nodo costituisce una componente distinta e le ricerche visitano circa 2.5 × 10^7 nodi.
Algoritmo
- Costruisci le liste degli archi uscenti e entranti di ogni nodo.
- Prendi il nodo successivo
ssenza una componente e conta una nuova componente. - Segna ciò che
sraggiunge lungo gli archi uscenti e ciò che lo raggiunge lungo gli archi entranti. - Ogni nodo segnato da entrambe le ricerche si unisce alla componente di
s. Quando ogni nodo ne ha una, restituisci il conteggio.
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 countAlgoritmo di Kosaraju: due passate
Intuizione
Nel grafo delle componenti, una componente è un pozzo, senza archi uscenti, e una ricerca avviata al suo interno trova esattamente quella componente. L’algoritmo di Kosaraju ordina le ricerche in modo che ciascuna si comporti così.
La prima passata elenca ogni nodo quando termina la sua ricerca in profondità. La seconda passata esplora il grafo invertito, che ha le stesse componenti, iniziando dall’ultimo nodo a terminare. Se un arco conduce dalla componente B alla C, l’ultimo nodo di B termina dopo tutti i nodi di C. Quindi, quando la seconda passata raggiunge C, tutte le componenti con un arco diretto verso C sono già state assegnate e, nel grafo invertito, la ricerca non può uscire da C.
Nel primo esempio, i nodi terminano nell’ordine 4, 3, 2, 1, 0, 5. La seconda passata raccoglie {5}, poi {0, 1, 2}, poi {3, 4}.
Algoritmo
- Costruisci gli elenchi degli archi uscenti e degli archi entranti.
- Esegui una ricerca in profondità iterativa da ogni nodo non visitato e aggiungi ogni nodo a
orderquando termina. - Esamina
orderpartendo dalla fine. Per ogni nodo che non appartiene a una componente, incrementa il conteggio di uno e avvia una ricerca da quel nodo lungo gli archi entranti, assegnando ogni nodo non assegnato che raggiunge. Restituisci il conteggio.
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 countAlgoritmo di Tarjan: una sola passata con valori low
Intuizione
Esegui una ricerca in profondità e numera ogni nodo nell’ordine in cui lo raggiungi: il suo index. Mantieni uno stack dei nodi visitati il cui componente è ancora aperto e un valore low: l’indice più piccolo che un nodo raggiunge scendendo nell’albero di ricerca e poi risalendo di un arco fino a un nodo presente nello stack.
Quando la visita di un nodo termina con low minore di index, qualcosa al di sotto risale fino a un nodo aperto precedente, quindi il nodo resta nello stack. Quando i due valori sono uguali, il nodo è il primo che la ricerca ha raggiunto nel suo componente: rimuovi dallo stack tutti i nodi fino a esso e conta un componente. Un arco che porta a un nodo rimosso dallo stack conduce a un componente già terminato che non può risalire, quindi viene ignorato.
Nel primo esempio, 3 rimuove {4, 3} e 0 rimuove {2, 1, 0}. L’arco del nodo 5 conduce al nodo 4, già rimosso dallo stack, quindi 5 viene rimosso da solo.
Algoritmo
- Per ogni nodo non visitato, assegnagli l’indice successivo, imposta
lowsullo stesso valore, inseriscilo nello stack dei nodi e inserisci il frame (node, first edge). - Se il nodo del frame in cima ha ancora un arco, seguilo: un target non visitato riceve un indice e un frame, mentre un target presente nello stack dei nodi abbassa
low[node]al suo indice. - Altrimenti rimuovi il frame e abbassa
lowdel nodo padre alow[node]. Selow[node]è uguale aindex[node], rimuovi nodi dallo stack dei nodi fino al nodo e conta una componente.
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
Trappole e casi limite
- Dimenticare i nodi senza archi. Nel secondo esempio, il nodo 4 non compare in alcun arco ed è comunque una componente.
- Abbassare
lowtramite qualsiasi nodo visitato invece che solo tramite quelli nello stack. Nel primo esempio, l’arco5 → 4impedisce quindi a 5 di chiudere la propria componente. - Trattare gli archi come bidirezionali. In questo modo si contano le componenti connesse: il primo esempio ne darebbe 1 invece di 3.
- Usare la ricorsione in Python. Un ciclo attraverso 5000 nodi annida 5000 chiamate, cinque volte il limite predefinito di 1000. Tieni un tuo stack di frame.
- Eseguire il secondo passaggio di Kosaraju sugli archi originali oppure nell’ordine in cui i nodi sono stati visitati per la prima volta. Entrambe le opzioni fondono componenti che raggiungono l’una l’altra in un solo senso.
Domande frequenti3
Qual è la complessità temporale per trovare le componenti fortemente connesse?
Tempo O(n + E) con l’algoritmo di Kosaraju o Tarjan, poiché ogni nodo e arco viene gestito un numero costante di volte. Entrambi usano spazio O(n + E) per gli elenchi degli archi e le pile di ricerca.
Dovresti usare l’algoritmo di Kosaraju o quello di Tarjan?
L’algoritmo di Kosaraju consiste in due semplici ricerche ed è più difficile sbagliarlo. Quello di Tarjan ne richiede una sola e non necessita di un grafo invertito, al costo di tenere traccia di low.
Qual è la differenza tra componenti fortemente connesse e componenti connesse?
Le componenti connesse ignorano la direzione degli archi: due nodi fanno parte della stessa componente quando esiste un percorso che li collega. Nelle componenti fortemente connesse, ogni nodo deve poter raggiungere l’altro. Il primo esempio è una componente connessa, ma tre componenti fortemente connesse.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def countSCC(n, edges):
# Scrivi il codice quiTest #1
Test #2
Argomenti
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
Output atteso
3