Connessione ridondante e rilevamento dei cicli
Rilevi l'arco che crea un ciclo in un grafo non orientato applicando union a ogni arco e verificando se due nodi sono già connessi.
Connessione ridondante e rilevamento dei cicli è 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 connessione ridondante?
Il problema Redundant Connection (LeetCode 684) fornisce un albero di n nodi e un arco aggiuntivo, che forma esattamente un ciclo. Il compito consiste nel trovare l'arco che, se rimosso, ripristina l'albero. Se esistono più risposte, occorre restituire l'ultimo arco nell'elenco di input.
Un albero con n nodi ha esattamente n-1 archi ed è connesso e privo di cicli. L'aggiunta di un altro arco crea esattamente un ciclo. L'arco aggiunto (ridondante) collega due nodi che appartenevano già alla stessa componente: è il classico scenario di rilevamento dei cicli con DSU.
# Example
# n=5, edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
# Adding edge [2,3] creates cycle 1-2-3-1
# So [2,3] is the redundant connection
# Key insight: process edges one by one with DSU
# The FIRST edge where both endpoints are already connected is the redundant one
print('Tree property: n nodes, n-1 edges, no cycles')
print('Adding 1 edge: n nodes, n edges, exactly 1 cycle')
print('DSU approach: find the edge that connects already-connected nodes')Rilevamento dei cicli con DSU
DSU rileva naturalmente i cicli: prima di aggiungere un arco (u, v), si verifica se find(u) == find(v). Se condividono la stessa radice, i due nodi sono già connessi e l'aggiunta di questo arco crea un ciclo. Questo è l'arco ridondante.
Questo approccio funziona per i grafi non diretti. Per ogni arco, si uniscono con successo le due componenti (nessun ciclo ancora presente) oppure si rileva che entrambi gli estremi appartengono già alla stessa componente (ciclo trovato). La complessità temporale è O(n × alpha(n)), quasi O(n).
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1)) # 1-indexed
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # same component => cycle found
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v] # this edge creates the cycle
edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
print(find_redundant_connection(edges)) # [2, 3]Esecuzione passo per passo dell'algoritmo
Analizziamo passo per passo [[1,2],[1,3],[2,3]]. Inizialmente, ogni nodo è la propria componente: {1}, {2}, {3}.
- Arco [1,2]: find(1)=1, find(2)=2, diversi — eseguiamo l'unione. Componenti: {1,2}, {3}
- Arco [1,3]: find(1)=root, find(3)=3, diversi — eseguiamo l'unione. Componenti: {1,2,3}
- Arco [2,3]: find(2)=root, find(3)=root — stessa radice! Ciclo rilevato. Restituiamo [2,3].
L'algoritmo elabora gli archi nell'ordine in cui compaiono e restituisce il primo arco che completa un ciclo. Poiché il problema garantisce un solo arco aggiuntivo, questo è sempre l'arco ridondante corretto.
def find_redundant_trace(edges):
parent = list(range(len(edges) + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
pu, pv = find(u), find(v)
print(f'Edge ({u},{v}): find({u})={pu}, find({v})={pv}', end=' => ')
if pu == pv:
print('CYCLE DETECTED!')
return [u, v]
parent[pv] = pu
print('merged')
return []
result = find_redundant_trace([[1,2],[1,3],[2,3]])
print('Redundant edge:', result)Rilevamento dei cicli nei grafi non diretti con DFS
Un'alternativa a DSU per rilevare i cicli nei grafi non diretti è la DFS con tracciamento del genitore. Durante la DFS, se si raggiunge un nodo già visitato che non è il genitore diretto del nodo corrente, è stato trovato un arco all'indietro, che indica la presenza di un ciclo.
L'approccio con DFS richiede tuttavia un tempo O(V + E) e restituisce l'informazione che esiste un ciclo, ma non identifica facilmente quale arco specifico sia ridondante. DSU è preferibile nei problemi che chiedono di identificare l'arco ridondante specifico, perché lo si trova naturalmente quando l'unione fallisce.
from collections import defaultdict
def has_cycle_dfs(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb == parent:
continue # skip the edge we came from
if nb in visited:
return True # back edge => cycle
if dfs(nb, node):
return True
return False
for node in range(1, n + 1):
if node not in visited:
if dfs(node, -1):
return True
return False
print(has_cycle_dfs(3, [[1,2],[1,3],[2,3]])) # True
print(has_cycle_dfs(3, [[1,2],[1,3]])) # FalseRilevamento dei cicli nei grafi diretti
Per i grafi diretti, il rilevamento dei cicli con DSU non funziona direttamente perché gli archi hanno una direzione. Si utilizza invece la DFS con marcatura a tre colori: bianco (non visitato), grigio (nel percorso DFS corrente), nero (elaborato completamente). Un arco all'indietro verso un nodo grigio indica la presenza di un ciclo.
In un grafo non diretto, qualsiasi arco all'indietro indica un ciclo. In un grafo diretto, un arco trasversale verso un nodo nero non indica un ciclo: solo gli archi all'indietro verso nodi grigi lo fanno. Questa distinzione è fondamentale e viene verificata nei problemi di course-schedule.
def has_cycle_directed(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
# 0=white(unvisited), 1=grey(in stack), 2=black(done)
color = [0] * (n + 1)
def dfs(node):
color[node] = 1 # grey: currently visiting
for nb in graph[node]:
if color[nb] == 1:
return True # back edge to grey node => cycle
if color[nb] == 0:
if dfs(nb):
return True
color[node] = 2 # black: fully processed
return False
for node in range(1, n + 1):
if color[node] == 0:
if dfs(node):
return True
return False
from collections import defaultdict
print(has_cycle_directed(3, [[1,2],[2,3],[3,1]])) # True: 1->2->3->1
print(has_cycle_directed(3, [[1,2],[1,3],[2,3]])) # FalseRedundant Connection II: variante per grafi diretti
LeetCode 685 estende il problema ai grafi diretti in cui ogni nodo ha esattamente un genitore (formando un albero radicato con un arco aggiuntivo). Si presentano due casi: un nodo ha due genitori (grado entrante pari a 2) oppure esiste un ciclo senza che alcun nodo abbia due genitori.
La soluzione cerca innanzitutto i nodi con grado entrante pari a 2. Se ne trova uno, una delle sue due entrate deve essere la risposta. In seguito, il rilevamento dei cicli con DSU determina quale dei due archi candidati rimuovere. Questo approccio in due fasi gestisce correttamente tutti i casi.
def find_redundant_directed(edges):
n = len(edges)
parent_map = {} # node -> its parent in the input
candidate1 = candidate2 = None
for u, v in edges:
if v in parent_map: # v already has a parent
candidate1 = [parent_map[v], v] # earlier edge
candidate2 = [u, v] # later edge
else:
parent_map[v] = u
# DSU cycle detection, skipping candidate2 if it exists
dsu = list(range(n + 1))
def find(x):
while dsu[x] != x: dsu[x] = dsu[dsu[x]]; x = dsu[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
dsu[px] = py; return True
for u, v in edges:
if candidate2 and [u, v] == candidate2: continue # skip candidate2
if not union(u, v): # cycle found without candidate2
return candidate1 if candidate1 else [u, v]
return candidate2 # no cycle when excluding candidate2 => candidate2 is redundant
print(find_redundant_directed([[1,2],[1,3],[2,3]])) # [2,3]
print(find_redundant_directed([[1,2],[2,3],[3,4],[4,1],[1,5]])) # [4,1]Validità del grafo dopo la rimozione di un arco
Dopo aver identificato l'arco ridondante, è possibile verificare il risultato controllando che la sua rimozione lasci un albero valido: esattamente n-1 archi, tutti i nodi connessi e nessun ciclo. Nel problema da colloquio, DSU garantisce naturalmente questa proprietà: se si restituisce l'arco per cui l'unione è fallita, rimuovendolo rimangono esattamente gli n-1 archi uniti con successo, che formano un albero ricoprente.
Questa garanzia rende DSU particolarmente adatta a questo problema: le unioni riuscite costruiscono progressivamente l'albero e l'unione fallita identifica l'unico arco che non ne fa parte.
def verify_tree(n, edges, removed_edge):
parent = list(range(n + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
components = n
for u, v in edges:
if [u, v] == removed_edge:
continue # skip the removed edge
pu, pv = find(u), find(v)
if pu == pv:
print('CYCLE DETECTED after removal! Wrong answer.')
return False
parent[pv] = pu
components -= 1
if components != 1:
print(f'Graph not connected ({components} components). Wrong answer.')
return False
print('Valid tree after removing edge:', removed_edge)
return True
edges = [[1,2],[1,3],[2,3]]
verify_tree(3, edges, [2,3])
verify_tree(3, edges, [1,2]) # wrong removalAnalisi della complessità temporale e spaziale
La soluzione di Redundant Connection basata su DSU elabora ciascuno degli n archi esattamente una volta e ogni operazione union/find ha un costo ammortizzato di O(alpha(n)). Tempo totale: O(n × alpha(n)), cioè effettivamente O(n).
La complessità spaziale è O(n) per gli array parent e rank. È ottimale: è necessario almeno leggere tutti gli n archi e memorizzare alcune informazioni per ogni nodo. Si consideri, in confronto, un approccio ingenuo che esegue DFS dopo ogni inserimento di un arco: richiede O(n²) di tempo e O(n + E) di spazio.
# Summary of complexities
complexity = {
'Naive (DFS after each edge)': {'time': 'O(n^2)', 'space': 'O(n)'},
'DSU (path compression + rank)': {'time': 'O(n * alpha(n))', 'space': 'O(n)'},
'Sorting + DSU (Kruskal style)': {'time': 'O(n log n)', 'space': 'O(n)'},
}
for approach, costs in complexity.items():
print(f'{approach}:')
print(f' Time: {costs["time"]}')
print(f' Space: {costs["space"]}')
print()
print('alpha(n) <= 4 for all practical n, so DSU is effectively O(n).')Caso limite: arco su sé stesso
Un arco su sé stesso [u, u] crea immediatamente un ciclo, poiché entrambi gli estremi sono lo stesso nodo. In DSU, find(u) == find(u) è sempre vero, quindi l'unione fallisce immediatamente e [u, u] viene restituito come arco ridondante.
La maggior parte dei vincoli dei problemi garantisce l'assenza di archi su sé stessi, ma il codice robusto dovrebbe gestire comunque questo caso. L'implementazione di DSU lo gestisce naturalmente senza casi speciali: il controllo del ciclo if find(u) == find(v) lo intercetta prima di tentare qualsiasi unione. Occorre sempre verificare il comportamento con input per i casi limite, come cappi su un singolo nodo e input delle dimensioni minime.
def find_redundant_robust(edges):
n = len(edges)
parent = list(range(n + 1))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for u, v in edges:
pu, pv = find(u), find(v)
if pu == pv:
return [u, v] # handles self-loops too: u==v => pu==pv always
parent[pv] = pu
return []
# Self-loop test
print(find_redundant_robust([[1,2],[2,2]])) # [2,2] self-loop
# Minimum tree test
print(find_redundant_robust([[1,2],[2,3],[1,3]])) # [1,3]
# Standard test
print(find_redundant_robust([[1,2],[1,3],[2,3],[2,4],[3,5]])) # [2,3]Generalizzazione del rilevamento dei cicli tra gli algoritmi
Esistono diversi algoritmi per rilevare i cicli, ciascuno adatto a scenari differenti:
- DSU: grafi non diretti, arrivo online degli archi, O(alpha(n)) per arco — ideale per contare i cicli o trovare l'arco ridondante
- DFS con tracciamento del genitore: grafi non diretti, tutti gli archi disponibili in anticipo, O(V+E) — ideale quando serve il percorso del ciclo
- DFS a tre colori: grafi diretti, rilevamento degli archi all'indietro, O(V+E) — ideale per course-schedule e ordinamento topologico
- Ordinamento topologico (di Kahn): grafi diretti, rileva i cicli tramite i nodi residui con grado entrante diverso da zero — ideale quando serve anche l'ordinamento
# When to use which cycle-detection method:
# Problem type => preferred algorithm
problems = [
('Redundant Connection (undirected)', 'DSU'),
('Course Schedule (directed)', 'DFS three-color or Kahn topological sort'),
('Detect cycle in undirected graph', 'DFS with parent tracking or DSU'),
('Find cycle members in directed graph', 'DFS three-color + backtrack'),
('Online graph edges with cycle check', 'DSU'),
('Minimum spanning tree validity', 'DSU (Kruskal)'),
]
for problem, solution in problems:
print(f'{problem}\n => {solution}\n')Soluzione completa con casi limite
Ecco una soluzione pronta per la produzione a Redundant Connection, che gestisce tutti i casi limite: nodi indicizzati a partire da 1, esattamente un arco ridondante e la garanzia che la sua rimozione lasci un albero valido. Utilizza la DSU ottimale con dimezzamento dei cammini e unione per rango.
Dopo averla inviata, provi il seguito: cosa succederebbe se il grafo potesse contenere più archi ridondanti? Sarebbe necessario tenere traccia di tutti gli archi che completano un ciclo e restituire l'ultimo nell'input. La stessa strategia greedy continuerebbe a funzionare, perché DSU elabora gli archi nell'ordine in cui compaiono.
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v]
return [] # should never reach here given valid input
test_cases = [
[[1,2],[1,3],[2,3]],
[[1,2],[2,3],[3,4],[1,4],[1,5]],
[[1,2],[1,3],[2,3],[2,4],[3,5]],
]
for tc in test_cases:
print(find_redundant_connection(tc))Verifica rapida
Metta alla prova la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: una connessione ridondante è un arco che collega due nodi già connessi in un grafo non diretto, DSU la rileva verificando find(u) == find(v) prima di eseguire union e restituendo quell'arco e i grafi diretti richiedono una DFS a tre colori o l'algoritmo di Kahn invece di DSU per il rilevamento dei cicli. Nella prossima lezione applicheremo DSU al problema accounts-merge, in cui le email sono i nodi e le email condivise tra account attivano le unioni.
Domande Frequenti
La lezione «Connessione ridondante e rilevamento dei cicli» è gratuita?
Sì — il testo completo di «Connessione ridondante e rilevamento dei cicli» è 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 «Connessione ridondante e rilevamento dei cicli»?
Rilevi l'arco che crea un ciclo in un grafo non orientato applicando union a ogni arco e verificando se due nodi sono già connessi. 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 «Connessione ridondante e rilevamento dei cicli»?
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
- DSU con compressione dei cammini
- Union per rango e limite dell'inversa di Ackermann
- Connessione ridondante e rilevamento dei cicli
- Unione di account e componenti connesse