Componenti fortemente connesse
Raggruppare i nodi raggiungibili reciprocamente con Tarjan
Componenti fortemente connesse è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cos'è una SCC
Una componente fortemente connessa è un gruppo massimale di nodi in cui ogni nodo può raggiungere tutti gli altri seguendo archi orientati.
Perché sono importanti
Collassare ogni SCC in un supernodo trasforma qualsiasi grafo orientato in un DAG. Questo rende facili da analizzare le dipendenze reciproche.
Tarjan in un'unica scansione
L'algoritmo di Tarjan trova tutte le SCC con una sola DFS. Ha complessità O(V + E), uguale a quella di una singola visita semplice.
Numeri di scoperta
Si assegna a ogni nodo un tempo di scoperta in base all'ordine in cui la DFS lo visita per la prima volta. Questi identificatori permettono di confrontare quale nodo è stato visitato prima.
disc = [-1] * n
timer = 0Il valore low-link
Il valore low-link di un nodo è il più piccolo identificatore di scoperta raggiungibile da esso, anche attraverso archi all'indietro. Questo valore individua il componente.
low = [-1] * nInserire nello stack
Quando la DFS entra in un nodo, si impostano disc e low, poi lo si inserisce in uno stack di nodi che potrebbero appartenere allo stesso componente.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = TrueAggiornare low dai figli
Dopo la ricorsione su un figlio non visitato, si propaga verso l'alto il suo valore low: low[u] diventa il minimo tra il proprio valore e quello di low del figlio.
dfs(v)
low[u] = min(low[u], low[v])Gestire gli archi all'indietro
Se un vicino è già nello stack, è un antenato appartenente a questa SCC. Si usa il suo disc per ridurre low[u].
elif on_stack[v]:
low[u] = min(low[u], disc[v])Individuare la radice di un componente
Quando low[u] è uguale a disc[u], il nodo u è la radice di una SCC. Tutti i nodi sopra di esso nello stack appartengono allo stesso componente.
Estrarre il componente
Quando si raggiunge una radice, si estraggono nodi dallo stack finché non si rimuove u. Il gruppo estratto è esattamente una componente fortemente connessa.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakKosaraju come alternativa
Si preferiscono due passaggi? L'algoritmo di Kosaraju esegue una DFS, inverte ogni arco, poi esegue una seconda DFS nell'ordine di completamento per estrarre le SCC.
Verifica rapida
Durante la DFS di Tarjan, per il nodo u vale low[u] == disc[u]. Che cosa indica?
Riepilogo: SCC con Tarjan
Si tengono traccia di disc e low in un'unica DFS, si inseriscono nello stack i nodi attivi e si estrae un componente quando low è uguale a disc. SCC in O(V+E). 🧩
Domande Frequenti
La lezione «Componenti fortemente connesse» è gratuita?
Sì — il testo completo di «Componenti fortemente connesse» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Componenti fortemente connesse»?
Raggruppare i nodi raggiungibili reciprocamente con Tarjan Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Componenti fortemente connesse»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Ordinamento topologico con l’algoritmo di Kahn
- Rilevare cicli nei grafi orientati
- Componenti fortemente connesse
- Ponti e punti di articolazione