DSU med path compression
Implementera find med path compression så att alla noder på vägen pekar direkt på roten, vilket ger nära O(1) amortiserad tidskomplexitet för find.
DSU med path compression är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad är Disjoint Set Union?
Disjoint Set Union (DSU), även kallad Union-Find, är en datastruktur som upprätthåller en samling disjunkta (icke-överlappande) mängder. Den stöder två centrala operationer: find (vilken mängd tillhör element x?) och union (slå samman mängderna som innehåller x och y). DSU passar utmärkt för problem med dynamisk konnektivitet, där grupper slås samman över tid men aldrig delas upp.
Varje element börjar i sin egen mängd. När vi bearbetar kanter eller relationer slår vi samman mängderna. Utmaningen är att göra detta effektivt — naiva implementationer tar O(n) per operation, men med optimeringar närmar vi oss O(1) amortiserad tid.
# Naive DSU without optimisations
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # each node is its own parent
def find(self, x):
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = pyProblemet med naiv find
I en naiv DSU går find(x) upp längs föräldrakeden tills den når en nod som pekar på sig själv (roten). Om trädet är balanserat är detta O(log n). Men om vi alltid förenar genom att länka den andra roten under den första kan vi skapa en kedja (ett degenererat träd) med längden n, vilket gör varje find O(n).
Anta att 0→1→2→3→4 förenas i denna ordning. Nod 0:s find-anrop måste gå igenom hela kedjan. Med path compression eliminerar vi detta problem genom att låta varje besökt nod peka direkt på roten under själva find-operationen.
# Worst case without compression: a chain
# parent = [1, 2, 3, 4, 4] => find(0) takes 4 steps
# After path compression: parent = [4, 4, 4, 4, 4] => find(0) takes 1 step
parent = [1, 2, 3, 4, 4]
print('Before:', parent)
# Simulate find(0) with naive approach
x = 0
steps = 0
while parent[x] != x:
x = parent[x]
steps += 1
print('Root:', x, 'Steps taken:', steps)Path compression: rekursiv i ett pass
Path compression modifierar find-operationen så att varje nod längs sökvägen uppdateras till att peka direkt på roten efter att roten har hittats. Framtida find-anrop för dessa noder blir O(1). Den rekursiva versionen gör detta elegant i ett enda pass.
Den centrala insikten är att vi, efter att det rekursiva anropet har returnerat roten, sätter self.parent[x] = root innan vi returnerar. Detta plattar till trädet — alla noder på sökvägen pekar nu direkt på roten. Det ändrar inte vilken mängd en nod tillhör; det förkortar bara framtida sökvägar.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)
print('Root of 0:', dsu.find(0))
print('Parent array after compression:', dsu.parent)Path compression: iterativ i två pass
Den iterativa versionen av path compression använder två pass: i det första passet går vi uppåt för att hitta roten, och i det andra passet besöker vi varje nod på sökvägen igen och uppdaterar dess förälder så att den pekar direkt på roten. Detta undviker overhead från rekursionsstacken och är säkert för mycket djupa träd nära Pythons rekursionsgräns.
I både den rekursiva och den iterativa metoden är korrektheten oförändrad — find returnerar fortfarande samma rot. Den enda skillnaden är att föräldrapekarna uppdateras som en bieffekt, vilket gör alla framtida find-anrop för dessa noder till O(1).
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root] # first pass: find root
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root # second pass: compress
x = nxt
return root
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
return True
return False # already connected
dsu = DSU(6)
for a, b in [(0,1),(1,2),(2,3),(3,4)]:
dsu.union(a, b)
print('Parent before find(0):', dsu.parent[:])
dsu.find(0)
print('Parent after find(0):', dsu.parent[:])Amorterad komplexitet för path compression
Path compression ensamt uppnår en amorterad tidskomplexitet på O(log n) per operation över en följd av m operationer. Varje find-operation kan vara dyr första gången en kedja traverseras, men den plattar till kedjan så att varje efterföljande find för dessa noder blir O(1). Det totala arbetet fördelas över många operationer.
Den formella analysen använder potentialfunktionsmetoden: DSU:ns potential minskar varje gång en nods förälderlänk kortas, och denna minskning betalar för traverseringskostnaden. Utan union by rank ger path compression ensamt O(log n) amorterad komplexitet — redan en enorm förbättring jämfört med naiva O(n).
# Demonstrating amortised benefit
import time
def build_chain(n):
parent = list(range(n))
for i in range(n - 1):
parent[i] = i + 1 # chain: 0->1->2->...->n-1
return parent
n = 1000
parent = build_chain(n)
# First find on a chain: visits n nodes
x = 0
root = x
while parent[root] != root:
root = parent[root]
# Compress
while parent[x] != root:
nxt = parent[x]; parent[x] = root; x = nxt
print('After first find, parent[0]:', parent[0]) # should be n-1
print('Second find cost: O(1) since parent[0] is now the root')Antal sammanhängande komponenter
En vanlig tillämpning av DSU är att räkna sammanhängande komponenter i en graf. Vi initierar en components-räknare till n (en per nod). Varje lyckad union (som slår samman två olika mängder) minskar räknaren med 1. I slutet innehåller räknaren antalet distinkta komponenter.
Detta är effektivare än att köra BFS eller DFS för konnektivitetsfrågor, särskilt när kanter tillkommer stegvis (online). DSU behandlar varje kant på nästan O(1) amorterad tid, oavsett när den tillkommer.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.components = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
self.parent[px] = py
self.components -= 1
return True
dsu = DSU(7)
edges = [(0,1),(1,2),(3,4),(5,6)]
for u, v in edges:
dsu.union(u, v)
print('Components:', dsu.components) # 4: {0,1,2}, {3,4}, {5,6}, {6 alone was merged}
# Node 6 is alone => 4 total: {0,1,2},{3,4},{5,6},{6} wait
# Let me recalculate: 7 nodes, 4 edges merged 4 pairs => 7-4=3... no
# {0,1,2} one union, {3,4} one, {5,6} one => 7-3=4 components
print('Expected: 4')DSU för grafproblem: Number of Provinces
Problemet Number of Provinces ger en n×n-adjacensmatris och frågar hur många grupper av direkt eller indirekt sammanbundna städer som finns. Detta är exakt ett problem med sammanhängande komponenter, som DSU löser på ett enkelt sätt. Vi itererar över alla par (i, j) där isConnected[i][j] == 1 och anropar union(i, j).
Efter att alla anslutningar har behandlats är dsu.components svaret. Detta är enklare och snabbare än att köra BFS från varje obesökt nod, och metoden hanterar matrisrepresentationen direkt utan att först bygga en adjacenslista.
def find_provinces(isConnected):
n = len(isConnected)
parent = list(range(n))
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:
parent[px] = py
return True
return False
count = n
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
if union(i, j):
count -= 1
return count
matrix = [[1,1,0],[1,1,0],[0,0,1]]
print(find_provinces(matrix)) # 2: cities {0,1} and {2}Varianter av path compression: halvering
Utöver komprimering i två pass finns en enklare variant i ett pass som kallas path halving: när vi går upp längs kedjan låter vi varje nod peka på sin förälders förälder i stället för på sin förälder. Detta halverar sökvägens längd vid varje traversering utan ett andra pass och uppnår samma amorterade komplexitet O(alpha(n)) när det kombineras med union by rank.
Path halving föredras ofta i tävlingsprogrammering eftersom det består av en enda tydlig loop utan rekursion eller en andra genomgång. Varje steg utför self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x].
class DSUHalving:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # point to grandparent
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
dsu = DSUHalving(8)
for u, v in [(0,1),(2,3),(4,5),(6,7),(0,2),(4,6),(0,4)]:
dsu.union(u, v)
print('All in one component:', dsu.find(0) == dsu.find(7))Kontroll av konnektivitet efter union-operationer
För att kontrollera om två noder är sammanbundna (tillhör samma komponent) anropar ni find(x) == find(y). Om båda returnerar samma rot tillhör de samma komponent. Detta är en konnektivitetsfråga, och med path compression körs den på nära O(1) amorterad tid.
I intervjuproblem förekommer konnektivitetsfrågor ofta blandade med union-operationer. DSU hanterar båda online — union-operationer och frågor kan varvas i valfri ordning. Detta skiljer DSU från statiska grafalgoritmer som BFS/DFS, som måste köras på nytt efter varje strukturell förändring.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
def connected(self, x, y):
return self.find(x) == self.find(y)
dsu = DSU(10)
dsu.union(0, 3)
dsu.union(3, 7)
dsu.union(1, 5)
print(dsu.connected(0, 7)) # True: 0-3-7
print(dsu.connected(0, 5)) # False: different components
print(dsu.connected(1, 5)) # True: 1-5Vanliga fallgropar vid implementering av DSU
Ett vanligt misstag är att anropa find och sedan ändra parent på fel sätt. Anropa alltid find för båda elementen innan ni kontrollerar likhet — annars kan ni felaktigt jämföra en nod med sin egen rot. En annan fallgrop är att glömma att union ska vara en tom operation när båda elementen redan delar rot.
I Python kan gränsen för rekursionsdjupet (standardvärde 1000) orsaka RecursionError för stora kedjor med rekursiv find. Använd antingen den iterativa versionen i två pass, höj gränsen med sys.setrecursionlimit eller använd path halving iterativt för att helt undvika djup rekursion.
import sys
sys.setrecursionlimit(10000) # needed for large recursive DSU
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
# Safe iterative path compression
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root
x = nxt
return root
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False # already same component — do nothing
self.parent[px] = py
return True
dsu = DSU(5)
print(dsu.union(0, 1)) # True: merged
print(dsu.union(0, 1)) # False: already merged — no double-countingSpårning av DSU-komponenters storlek
I vissa problem behöver ni storleken på varje komponent, inte bara dess rot. Lägg till en size-array som initieras med enbart 1:or. När två komponenter slås samman lägger ni den mindre rotens storlek till den större rotens. Detta möjliggör O(1)-frågor om komponentstorlek efter varje union.
Storleksspårning är också grunden för union by size (ett alternativ till union by rank): fäst alltid det mindre trädet under roten till det större trädet. Detta garanterar att trädets höjd förblir O(log n), vilket ger samma asymptotiska garanti som union by rank.
class DSUWithSize:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return
if self.size[px] < self.size[py]:
px, py = py, px # attach smaller under larger
self.parent[py] = px
self.size[px] += self.size[py]
def get_size(self, x):
return self.size[self.find(x)]
dsu = DSUWithSize(6)
for u, v in [(0,1),(1,2),(3,4)]:
dsu.union(u, v)
print('Size of component containing 0:', dsu.get_size(0)) # 3
print('Size of component containing 3:', dsu.get_size(3)) # 2
print('Size of component containing 5:', dsu.get_size(5)) # 1Snabbkontroll
Testa er förståelse av begreppen inom Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionens sammanfattning
I den här lektionen lärde ni er att DSU upprätthåller disjunkta mängder med find- och union-operationer, att path compression plattar till trädet genom att låta alla traverserade noder peka direkt på roten och att detta ger en find-prestanda nära O(1) amorterat. Nästa steg är union by rank, som håller träden grunda uppifrån och ned för att uppnå den inversa Ackermann-gränsen.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”DSU med path compression” gratis?
Ja – hela texten till ”DSU med path compression” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”DSU med path compression”?
Implementera find med path compression så att alla noder på vägen pekar direkt på roten, vilket ger nära O(1) amortiserad tidskomplexitet för find. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”DSU med path compression”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- DSU med path compression
- Union by rank och den inversa Ackermann-gränsen
- Redundant Connection och cykeldetektering
- Accounts Merge och sammanhängande komponenter