Redundant forbindelse og cykeldetektion
Find den kant, der skaber en cykel i en ikke-rettet graf, ved at udføre union for hver kant og kontrollere, om to noder allerede er forbundet.
Redundant forbindelse og cykeldetektion er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad er en overflødig kant
Problemet med den overflødige kant (LeetCode 684) giver dig et træ med n knuder og én ekstra kant, som danner præcis én cyklus. Din opgave er at finde den kant, der gendanner træet, når den fjernes. Hvis der findes flere svar, skal du returnere det sidste på inputlisten.
Et træ med n knuder har præcis n-1 kanter og er sammenhængende uden cyklusser. Når du tilføjer endnu en kant, opstår der præcis én cyklus. Den tilføjede (overflødige) kant forbinder to knuder, der allerede lå i samme komponent — et klassisk scenarie for cyklusdetektion 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')Cyklusdetektion med DSU
DSU opdager cyklusser naturligt: Før en kant (u, v) tilføjes, skal du kontrollere, om find(u) == find(v). Hvis de deler en rod, er de allerede forbundne — tilføjelsen af denne kant skaber en cyklus. Dette er den overflødige kant.
Denne metode fungerer for urettede grafer. For hver kant forbinder vi enten de to komponenter korrekt (endnu ingen cyklus), eller også opdager vi, at begge endepunkter allerede ligger i samme komponent (cyklus fundet). Tidskompleksiteten er O(n × alpha(n)), hvilket næsten er 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]Gennemgang af algoritmen
Lad os gennemgå [[1,2],[1,3],[2,3]] trin for trin. I begyndelsen er hver knude sin egen komponent: {1}, {2}, {3}.
- Kant [1,2]: find(1)=1, find(2)=2, forskellige — udfør union på dem. Komponenter: {1,2}, {3}
- Kant [1,3]: find(1)=rod, find(3)=3, forskellige — udfør union på dem. Komponenter: {1,2,3}
- Kant [2,3]: find(2)=rod, find(3)=rod — samme rod! Cyklus fundet. Returnér [2,3].
Algoritmen behandler kanterne i rækkefølge og returnerer den første kant, der fuldender en cyklus. Fordi opgaven garanterer præcis én ekstra kant, er dette altid den korrekte overflødige kant.
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)Cyklusdetektion i urettede grafer med DFS
Et alternativ til DSU til cyklusdetektion i urettede grafer er DFS med sporing af forældre. Under DFS har vi fundet en tilbagekant, hvis vi når frem til en knude, der allerede er besøgt og ikke er den aktuelle knudes direkte forælder — det angiver en cyklus.
DFS-metoden kræver dog O(V + E) tid og afgør, om der findes en cyklus, men angiver ikke nemt, hvilken specifik kant der er overflødig. DSU foretrækkes i problemer, hvor du skal identificere den specifikke overflødige kant, fordi du naturligt finder den, når sammenføjningen 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]])) # FalseCyklusdetektion i rettede grafer
For rettede grafer fungerer cyklusdetektion med DSU ikke direkte, fordi kanterne har en retning. Brug i stedet DFS med markering i tre farver: hvid (ubesøgt), grå (i den aktuelle DFS-sti) og sort (fuldt behandlet). En tilbagekant til en grå knude angiver en cyklus.
I en urettet graf betyder enhver tilbagekant, at der er en cyklus. I en rettet graf er en krydskant til en sort knude ikke en cyklus — kun tilbagekanter til grå knuder er det. Denne forskel er afgørende og afprøves i kursusplanlægningsproblemer.
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]])) # FalseOverflødig kant II: variant for rettede grafer
LeetCode 685 udvider problemet til rettede grafer, hvor hver knude har præcis én forælder (så der dannes et rodfæstet træ med én ekstra kant). Der opstår to tilfælde: enten har en knude to forældre (indgrad 2), eller også er der en cyklus, uden at nogen knude har to forældre.
Løsningen leder først efter knuder med indgrad 2. Hvis en sådan findes, må en af dens to indgående kanter være svaret. Derefter afgør cyklusdetektion med DSU, hvilken af de to kandidatkanter der skal fjernes. Denne totrinsmetode håndterer alle tilfælde 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 gyldighed efter fjernelse af en kant
Efter at have identificeret den overflødige kant kan vi kontrollere resultatet ved at sikre, at en gyldig træstruktur er tilbage, når den fjernes: præcis n-1 kanter, alle knuder forbundne og ingen cyklusser. I interviewopgaven garanterer DSU naturligt dette — hvis vi returnerer den kant, hvor sammenføjningen mislykkedes, har vi efter fjernelsen præcis de n-1 kanter, der blev forbundet korrekt, og de danner et udspændende træ.
Det er grunden til, at DSU er så velegnet til dette problem: Vellykkede sammenføjninger bygger træet gradvist, og den mislykkede sammenføjning identificerer den ene kant, der ikke hører til.
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 af tids- og pladskompleksitet
Den DSU-baserede løsning på problemet med den overflødige kant behandler hver af de n kanter præcis én gang, og hver sammenføjnings-/find-operation koster amortiseret O(alpha(n)). Samlet tid: O(n × alpha(n)), hvilket i praksis er O(n).
Pladskompleksiteten er O(n) for forælder- og rangtabellerne. Dette er optimalt — du skal som minimum læse alle n kanter og gemme en form for tilstand pr. knude. Sammenlign dette med en naiv tilgang, der kører DFS efter hver kanttilføjelse: O(n²) tid og O(n + E) plads.
# 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).')Kanttilfælde: Selvløkke
En selvløkke [u, u] skaber straks en cyklus, fordi begge endepunkter er den samme knude. I DSU er find(u) == find(u) altid sandt, så sammenføjningen mislykkes straks, og [u, u] returneres som den overflødige kant.
De fleste opgavebegrænsninger garanterer, at der ikke findes selvløkker, men robust kode bør håndtere dem. DSU-implementeringen håndterer dem naturligt uden et særtilfælde — cykluskontrollen if find(u) == find(v) opfanger det, før der forsøges en sammenføjning. Kontrollér altid med kanttilfælde som løkker med én knude og input med minimumsstø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 af cyklusdetektion på tværs af algoritmer
Flere algoritmer detekterer cyklusser, og hver passer til forskellige scenarier:
- DSU: urettede grafer, kanter ankommer online, O(alpha(n)) pr. kant — bedst til at tælle eller finde den overflødige kant
- DFS med sporing af forældre: urettede grafer, alle kanter kendt på forhånd, O(V+E) — bedst, når du har brug for cyklusstien
- DFS med tre farver: rettede grafer, detektion af tilbagekanter, O(V+E) — bedst til kursusplanlægning og topologisk sortering
- Topologisk sortering (Kahns): rettede grafer, detekterer en cyklus via resterende knuder med indgrad større end nul — bedst, når du også har brug for en rækkefølge
# 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')Komplet løsning med kanttilfælde
Her er en produktionsklar løsning på problemet med den overflødige kant, som håndterer alle kanttilfælde: 1-indekserede knuder, præcis én overflødig kant og garantien for, at fjernelsen af den efterlader et gyldigt træ. Den bruger den optimale DSU med halvering af stier og sammenføjning efter rang.
Efter indsendelsen kan du prøve det opfølgende spørgsmål: Hvad nu, hvis grafen kunne have flere overflødige kanter? Du skulle holde styr på alle kanter, der fuldender en cyklus, og returnere den sidste på inputlisten — den samme grådige strategi virker stadig, fordi DSU behandler kanterne i rækkefø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))Hurtigt tjek
Afprøv din forståelse af begreberne i Data Structures & Algorithms — Coding Interview Prep fra denne lektion.
Opsummering af lektionen
I denne lektion lærte du: en overflødig kant forbinder to allerede forbundne knuder i en urettet graf, DSU detekterer dette ved at kontrollere find(u) == find(v) før kaldet til union og returnere den pågældende kant, og rettede grafer kræver DFS med tre farver eller Kahns algoritme i stedet for DSU til cyklusdetektion. Næste gang anvender vi DSU på problemet med sammenlægning af konti, hvor e-mailadresserne er knuderne, og delte e-mailadresser mellem konti udløser sammenføjninger.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Redundant forbindelse og cykeldetektion” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Redundant forbindelse og cykeldetektion”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Redundant forbindelse og cykeldetektion”?
Find den kant, der skaber en cykel i en ikke-rettet graf, ved at udføre union for hver kant og kontrollere, om to noder allerede er forbundet. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Redundant forbindelse og cykeldetektion”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- DSU med sti-komprimering
- Union efter rang og den inverse Ackermann-grænse
- Redundant forbindelse og cykeldetektion
- Sammenfletning af konti og sammenhængende komponenter