Redundant forbindelse og sykeloppdagelse
Oppdag kanten som oppretter en sykel i en urettet graf ved å utføre union for hver kant og kontrollere om to noder allerede er sammenkoblet.
Redundant forbindelse og sykeloppdagelse er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva er en overflødig kant?
Problemet Redundant Connection (LeetCode 684) gir en trestruktur med n noder og én ekstra kant, som danner nøyaktig én syklus. Oppgaven er å finne kanten som må fjernes for å gjenopprette trestrukturen. Hvis flere svar er mulige, skal den siste i inndatalisten returneres.
Et tre med n noder har nøyaktig n-1 kanter og er sammenhengende uten sykluser. Når én kant til legges til, oppstår nøyaktig én syklus. Den ekstra (overflødige) kanten kobler sammen to noder som allerede var i samme komponent — et klassisk scenario for syklusdeteksjon med 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')Syklusdeteksjon med DSU
DSU oppdager sykluser på en naturlig måte: Før en kant (u, v) legges til, kontrolleres det om find(u) == find(v). Hvis de har samme rot, er de allerede koblet sammen — og denne kanten skaper en syklus. Dette er den overflødige kanten.
Denne tilnærmingen fungerer for urettede grafer. For hver kant utfører vi enten union på de to komponentene (ingen syklus ennå), eller oppdager at begge endepunktene allerede er i samme komponent (syklus funnet). Tidskompleksiteten er O(n × alpha(n)), altså nesten 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]Gjennomgang av algoritmen
Vi går trinnvis gjennom [[1,2],[1,3],[2,3]]. Til å begynne med er hver node sin egen komponent: {1}, {2}, {3}.
- Kant [1,2]: find(1)=1, find(2)=2, ulike — utfør union på dem. Komponenter: {1,2}, {3}
- Kant [1,3]: find(1)=rot, find(3)=3, ulike — utfør union på dem. Komponenter: {1,2,3}
- Kant [2,3]: find(2)=rot, find(3)=rot — samme rot! Syklus oppdaget. Returner [2,3].
Algoritmen behandler kantene i rekkefølge og returnerer den første kanten som fullfører en syklus. Siden problemet garanterer nøyaktig én ekstra kant, er dette alltid den riktige overflødige kanten.
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)Syklusdeteksjon i urettede grafer med DFS
Et alternativ til DSU for syklusdeteksjon i urettede grafer er DFS med sporing av forelder. Under DFS har vi funnet en tilbakekant hvis vi når en node som allerede er besøkt, og som ikke er den gjeldende nodens direkte forelder — noe som viser at det finnes en syklus.
DFS-tilnærmingen krever imidlertid O(V + E) tid og angir om det finnes en syklus, men gjør det ikke enkelt å finne den konkrete overflødige kanten. DSU foretrekkes i problemer der den spesifikke overflødige kanten skal identifiseres, fordi den finnes naturlig når union-operasjonen mislykkes.
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]])) # FalseSyklusdeteksjon i rettede grafer
For rettede grafer fungerer ikke syklusdeteksjon med DSU direkte, fordi kantene har en retning. Bruk i stedet DFS med markering i tre farger: hvit (ikke besøkt), grå (i den gjeldende DFS-stien) og svart (ferdig behandlet). En tilbakekant til en grå node indikerer en syklus.
I en urettet graf betyr enhver tilbakekant at det finnes en syklus. I en rettet graf utgjør en krysskant til en svart node ikke en syklus — bare tilbakekanter til grå noder gjør det. Dette skillet er avgjørende og testes i problemer om kursplanlegging.
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: Rettet variant
LeetCode 685 utvider problemet til rettede grafer der hver node har nøyaktig én forelder (en rotfestet trestruktur med én ekstra kant). Det oppstår to tilfeller: enten har en node to foreldre (inngrad 2), eller så finnes det en syklus uten at noen node har to foreldre.
Løsningen ser først etter noder med inngrad 2. Hvis en slik node finnes, må én av de to innkommende kantene være svaret. Deretter avgjør syklusdeteksjon med DSU hvilken av de to kandidatkantene som skal fjernes. Denne tofasede tilnærmingen håndterer alle tilfeller korrekt.
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]Grafens gyldighet etter fjerning av en kant
Etter at den overflødige kanten er identifisert, kan resultatet kontrolleres ved å sjekke at fjerningen gir et gyldig tre: nøyaktig n-1 kanter, alle noder sammenhengende og ingen sykluser. I intervjuproblemet garanterer DSU dette naturlig — hvis kanten som fikk union-operasjonen til å mislykkes, returneres, står vi igjen med nøyaktig de n-1 kantene som ble koblet sammen, og disse utgjør et spennende tre.
Det er denne garantien som gjør DSU så ryddig for dette problemet: Vellykkede unioner bygger treet trinnvis, og den mislykkede unionen identifiserer den ene kanten som ikke hører hjemme.
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 removalAnalyse av tids- og plasskompleksitet
Den DSU-baserte løsningen på Redundant Connection behandler hver av de n kantene nøyaktig én gang, og hver union/find-operasjon koster amortisert O(alpha(n)). Total tid: O(n × alpha(n)), i praksis O(n).
Plasskompleksiteten er O(n) for foreldre- og rangtabellene. Dette er optimalt — det er som et minimum nødvendig å lese alle de n kantene og lagre noe tilstand per node. Til sammenligning bruker en naiv tilnærming som kjører DFS etter hver kantinnsetting, O(n²) tid og O(n + E) plass.
# 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).')Randtilfelle: Selvløkke
En selvløkke [u, u] skaper umiddelbart en syklus, siden begge endepunktene er den samme noden. I DSU er find(u) == find(u) alltid sant, så union-operasjonen mislykkes umiddelbart, og [u, u] returneres som den overflødige kanten.
De fleste problembegrensninger garanterer at det ikke finnes selvløkker, men robust kode bør håndtere dette. DSU-implementasjonen håndterer det naturlig uten noe spesialtilfelle — sykluskontrollen if find(u) == find(v) fanger det opp før en union forsøkes. Kontroller alltid med inndata som dekker randtilfeller, for eksempel løkker på én node og inndata med minst mulig størrelse.
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]Generalisering av syklusdeteksjon på tvers av algoritmer
Flere algoritmer oppdager sykluser, og hver av dem passer til ulike scenarioer:
- DSU: urettede grafer, kanter kommer online, O(alpha(n)) per kant — best for å telle eller finne den overflødige kanten
- DFS med sporing av forelder: urettede grafer, alle kanter er kjent på forhånd, O(V+E) — best når syklusbanen trengs
- DFS med tre farger: rettede grafer, oppdager tilbakekanter, O(V+E) — best for problemer om kursplanlegging og topologisk sortering
- Topologisk sortering (Kahns): rettede grafer, oppdager sykluser gjennom noder med gjenværende inngrad ulik null — best når en rekkefølge også trengs
# 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')Fullstendig løsning med randtilfeller
Her er en produksjonsklar løsning på Redundant Connection som håndterer alle randtilfeller: 1-indekserte noder, nøyaktig én overflødig kant og garantien om at fjerningen av den gir et gyldig tre. Den bruker optimal DSU med path halving og union by rank.
Etter innsendingen kan De prøve oppfølgeren: Hva om grafen kunne ha flere overflødige kanter? Da måtte alle kanter som fullfører en syklus, spores, og den siste i inndataen returneres — den samme grådige strategien fungerer fortsatt fordi DSU behandler kantene i rekkefølge.
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))Hurtigsjekk
Test forståelsen av begrepene Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte De: en overflødig forbindelse er en kant som kobler sammen to noder som allerede er sammenhengende i en urettet graf, DSU oppdager dette ved å kontrollere find(u) == find(v) før union og returnere denne kanten, og rettede grafer krever DFS med tre farger eller Kahns algoritme i stedet for DSU for syklusdeteksjon. Deretter brukes DSU på kontosammenslåingsproblemet Accounts Merge, der e-postadresser er nodene, og felles e-postadresser mellom kontoer utløser unioner.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Redundant forbindelse og sykeloppdagelse» gratis?
Ja – hele teksten i «Redundant forbindelse og sykeloppdagelse» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Redundant forbindelse og sykeloppdagelse»?
Oppdag kanten som oppretter en sykel i en urettet graf ved å utføre union for hver kant og kontrollere om to noder allerede er sammenkoblet. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.
Hvor lang tid tar leksjonen «Redundant forbindelse og sykeloppdagelse»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- DSU med banekomprimering
- Union etter rang og den inverse Ackermann-grensen
- Redundant forbindelse og sykeloppdagelse
- Kontosammenslåing og sammenhengende komponenter