Łączenie według rangi i ograniczenie odwrotną funkcją Ackermanna
Dodawać łączenie według rangi, aby utrzymywać płaską strukturę drzew, oraz rozumieć, dlaczego połączenie obu optymalizacji daje zamortyzowany czas O(alpha(n)), czyli w praktyce stały
Łączenie według rangi i ograniczenie odwrotną funkcją Ackermanna to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Dlaczego drzewa rosną bez rangi
Sama kompresja ścieżki zapobiega powstawaniu wysokich drzew po przejściu przez nie, ale podczas początkowych operacji union nadal możemy utworzyć wysokie drzewo, jeśli zawsze dołączamy korzeń większego drzewa do mniejszego. Łączenie według rangi rozwiązuje ten problem, śledząc górne ograniczenie wysokości drzewa (rangę) i zawsze dołączając płytsze drzewo do głębszego.
Ranga nie jest dokładnie wysokością — kompresja ścieżki może zmniejszyć wysokość poniżej rangi — ale stanowi jej górne ograniczenie. Zachowując głębsze drzewo jako nowy korzeń, zapewniamy, że ranga zwiększa się tylko wtedy, gdy łączą się drzewa o tej samej randze, co ogranicza maksymalną rangę do O(log n).
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n # initially all trees have rank 0
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:
return False
# Attach lower-rank tree under higher-rank tree
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 # only increases when ranks are equal
return TrueTrzy przypadki łączenia według rangi
Podczas łączenia dwóch składowych o korzeniach px i py występują trzy przypadki zależne od ich rang:
- rank[px] > rank[py]: dołącz py do px — ranga px pozostaje bez zmian
- rank[px] < rank[py]: dołącz px do py — ranga py pozostaje bez zmian
- rank[px] == rank[py]: dołącz py do px (lub odwrotnie) — ranga nowego korzenia zwiększa się o 1
Ranga zwiększa się tylko w przypadku równych rang. Oznacza to, że ranga n wymaga co najmniej 2^n węzłów, więc maksymalna ranga wynosi O(log n). Dzięki temu ścieżki operacji find pozostają krótkie nawet bez kompresji ścieżki.
# Illustrating rank behaviour with 8 nodes
dsu_parent = list(range(8))
dsu_rank = [0] * 8
def find(x):
while dsu_parent[x] != x:
x = dsu_parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return
if dsu_rank[px] < dsu_rank[py]:
px, py = py, px
dsu_parent[py] = px
if dsu_rank[px] == dsu_rank[py]:
dsu_rank[px] += 1
# Build balanced tree step by step
union(0,1); union(2,3); union(4,5); union(6,7)
union(0,2); union(4,6)
union(0,4)
print('Ranks:', dsu_rank) # max rank <= log2(8) = 3
print('Root of all:', find(0))Połączenie kompresji ścieżki i łączenia według rangi
Gdy jednocześnie stosujemy kompresję ścieżki i łączenie według rangi, zamortyzowany czas operacji spada do O(alpha(n)) — odwrotnej funkcji Ackermanna. Dla każdego praktycznego rozmiaru danych wejściowych (do 2^65536) alpha(n) wynosi co najwyżej 4. W praktyce jest to czas stały.
Kompresja ścieżki spłaszcza drzewa od dołu po przejściu przez nie, podczas gdy łączenie według rangi zapobiega ich wzrostowi od góry podczas scalania. Te metody wzajemnie się uzupełniają: ranga ogranicza początkową głębokość, a kompresja eliminuje tę głębokość po pierwszym przejściu.
class OptimalDSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x): # path compression
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y): # union by rank
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 = OptimalDSU(1000)
import random; random.seed(42)
for _ in range(5000):
dsu.union(random.randint(0,999), random.randint(0,999))
print('Max rank reached:', max(dsu.rank)) # stays very smallZrozumienie odwrotnej funkcji Ackermanna
Funkcja Ackermanna A(m, n) rośnie niezwykle szybko — szybciej niż każda funkcja pierwotnie rekurencyjna. Jej odwrotność, alpha(n), jest zdefiniowana jako najmniejsze m, dla którego A(m, m) >= n. Ponieważ funkcja Ackermanna rośnie tak szybko, alpha(n) rośnie niewyobrażalnie wolno.
Dla n = 10^80 (liczby atomów w obserwowalnym wszechświecie) alpha(n) nadal wynosi tylko 4. Dlatego DSU z obiema optymalizacjami uznaje się w każdym praktycznym zastosowaniu za strukturę o efektywnie stałym czasie działania. W rzeczywistym problemie nigdy nie spotkają się Państwo z rozmiarem danych wystarczająco dużym, aby alpha(n) przekroczyło 5.
# Showing how slowly alpha(n) grows
# alpha(n) = smallest m such that A(m,m) >= n
# A(0,n) = n+1
# A(1,n) = n+2
# A(2,n) = 2n+3
# A(3,n) = 2^(n+3) - 3
# A(4,4) = 2^(2^(2^(2^2))) - 3 which is astronomically large
alpha_thresholds = {
1: 'n=1',
2: 'n up to 3',
3: 'n up to about 2048',
4: 'n up to 10^19728 (far beyond atoms in universe)',
5: 'essentially unreachable in practice',
}
for k, v in alpha_thresholds.items():
print(f'alpha(n)={k}: {v}')
print('\nConclusion: DSU operations are effectively O(1) for all real inputs.')Ranga czy rozmiar: co wybrać
Alternatywą dla łączenia według rangi jest łączenie według rozmiaru: zawsze dołączamy drzewo o mniejszym rozmiarze do drzewa o większym rozmiarze. Oba podejścia zapewniają gwarancję wysokości O(log n). Łączenie według rozmiaru często ułatwia rozumowanie, ponieważ rozmiary są dokładnymi wartościami, podczas gdy rangi stanowią górne ograniczenia i po kompresji mogą nie odzwierciedlać rzeczywistej wysokości.
Na rozmowach rekrutacyjnych oba podejścia są akceptowalne. Łączenie według rozmiaru ma dodatkową zaletę: bez dodatkowych obliczeń udostępnia rozmiary składowych, których wymaga wiele zadań. Łączenie według rangi jest nieco bardziej eleganckie z teoretycznego punktu widzenia i odpowiada oryginalnemu dowodowi Tarjana dotyczącymi ograniczenia przez odwrotną funkcję Ackermanna.
class DSUBySize:
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 False
if self.size[px] < self.size[py]:
px, py = py, px # always attach smaller under larger
self.parent[py] = px
self.size[px] += self.size[py]
return True
dsu = DSUBySize(8)
for u, v in [(0,1),(2,3),(0,2),(4,5),(6,7),(4,6),(0,4)]:
dsu.union(u, v)
print('Size of giant component:', dsu.size[dsu.find(0)])Zarys dowodu: dlaczego ranga pozostaje na poziomie O(log n)
Możemy indukcyjnie dowieść, że drzewo DSU o randze r zawiera co najmniej 2^r węzłów. Przypadek bazowy: ranga 0 oznacza pojedynczy węzeł (2^0 = 1). Krok indukcyjny: ranga r zwiększa się tylko wtedy, gdy łączą się dwa drzewa o randze r-1. Z założenia indukcyjnego każde poddrzewo ma co najmniej 2^(r-1) węzłów, więc połączone drzewo ma co najmniej 2 × 2^(r-1) = 2^r węzłów.
Ponieważ drzewo o randze r ma co najmniej 2^r węzłów, a łącznie mamy n węzłów, maksymalna ranga wynosi co najwyżej log₂(n). Oznacza to, że operacja find bez kompresji ścieżki zajmuje O(log n), a z kompresją ścieżki jej koszt zamortyzowany spada jeszcze bardziej.
# Verify the 2^rank lower bound empirically
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * 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.rank[px] < self.rank[py]: px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
if self.rank[px] == self.rank[py]: self.rank[px] += 1
n = 32
dsu = DSU(n)
for i in range(n - 1): dsu.union(i, i + 1)
for root in range(n):
if dsu.find(root) == root:
r = dsu.rank[root]
print(f'Root {root}: rank={r}, size={dsu.size[root]}, 2^rank={2**r}')Szablon DSU do programowania konkursowego
W programowaniu konkursowym i podczas rozmów rekrutacyjnych potrzebują Państwo sprawdzonego w praktyce szablonu DSU, który jest krótki, poprawny i obsługuje wszystkie przypadki brzegowe. Poniższy szablon wykorzystuje połówkowanie ścieżki (kompresję jednoprzebiegową) w połączeniu z łączeniem według rozmiaru — jest to zestaw łatwy do szybkiego napisania i całkowicie eliminuje rekurencję.
Zawsze inicjalizuj parent[i] = i oraz size[i] = 1. Pamiętaj, że po operacji find wartość size korzenia odzwierciedla rozmiar całej składowej. Nigdy nie używaj bezpośrednio size[x] — zawsze wywołuj size[find(x)].
class DSU:
def __init__(self, n):
self.p = list(range(n))
self.sz = [1] * n
def find(self, x):
while self.p[x] != x:
self.p[x] = self.p[self.p[x]] # path halving
x = self.p[x]
return x
def union(self, x, y):
x, y = self.find(x), self.find(y)
if x == y: return False
if self.sz[x] < self.sz[y]: x, y = y, x
self.p[y] = x
self.sz[x] += self.sz[y]
return True
def same(self, x, y): return self.find(x) == self.find(y)
def size(self, x): return self.sz[self.find(x)]
# Usage
dsu = DSU(10)
dsu.union(0, 5)
dsu.union(5, 9)
print(dsu.same(0, 9)) # True
print(dsu.size(0)) # 3Kiedy DSU nie wystarcza
DSU obsługuje łączenie zbiorów, ale nie obsługuje ich dzielenia z powrotem na dwa zbiory. Jeśli zadanie wymaga zarówno łączenia, jak i rozdzielania grup, potrzebują Państwo innej struktury (takiej jak drzewo link-cut). DSU nie przechowuje również natywnie elementów każdej grupy — potrzebna jest do tego dodatkowa lista sąsiedztwa lub słownik.
Ponadto standardowy DSU bez modyfikacji nie obsługuje ważonych krawędzi (ważony DSU jest bardziej zaawansowanym wariantem). W zadaniach takich jak znajdowanie najtańszej ścieżki między połączonymi węzłami bardziej odpowiednie są algorytmy Dijkstry lub BFS. Rozpoznanie zakresu zastosowań DSU pozwala uniknąć jego niewłaściwego użycia.
# DSU is perfect for: connected-components, cycle detection,
# Kruskal's MST, accounts-merge, number-of-provinces
# DSU is NOT suitable for:
# - Splitting/removing edges from a group
# - Finding the actual path between two nodes
# - Storing all members of a group efficiently
# - Directed graphs (without modification)
# Example of storing group members alongside DSU
from collections import defaultdict
class DSUWithMembers:
def __init__(self, n):
self.p = list(range(n))
self.members = defaultdict(set)
for i in range(n): self.members[i].add(i)
def find(self, x):
while self.p[x] != x: self.p[x] = self.p[self.p[x]]; x = self.p[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
self.members[px] |= self.members[py]
del self.members[py]
self.p[py] = pxPorównanie DSU z BFS/DFS pod kątem spójności
Zarówno BFS/DFS, jak i DSU rozwiązują zapytania o spójność w statycznych grafach, ale mają różne zalety. BFS/DFS działa w czasie O(V + E) i może znaleźć rzeczywistą ścieżkę między węzłami. DSU odpowiada na wiele zapytań o spójność dla stopniowo powiększających się zbiorów krawędzi, wykonując każde zapytanie w czasie bliskim O(1) — jest więc idealne dla algorytmów online, w których krawędzie pojawiają się pojedynczo.
Jeśli wszystkie krawędzie są znane od początku i potrzebują Państwo tylko sprawdzać spójność, obie metody się sprawdzą. Jeśli krawędzie są dodawane dynamicznie i trzeba odpowiadać na zapytania o spójność po dodaniu każdej kolejnej krawędzi, DSU jest zdecydowanie lepszym wyborem. W zadaniach, w których potrzebna jest również najkrótsza ścieżka, należy pozostać przy BFS.
# Comparing DSU vs BFS for 1000 nodes, 2000 edges
# After all edges given => BFS works fine
# But with online edge arrival + interleaved queries => DSU shines
from collections import deque
def bfs_connected(graph, src, dst, n):
visited = set([src])
q = deque([src])
while q:
node = q.popleft()
if node == dst: return True
for nb in graph.get(node, []):
if nb not in visited:
visited.add(nb); q.append(nb)
return False
# DSU for same query:
# dsu.same(src, dst) -- O(alpha(n)) amortised
# BFS for same query:
# O(V + E) every time -- not suitable for repeated queries
print('DSU is preferred for repeated connectivity queries.')
print('BFS/DFS is preferred when you also need the actual path.')Ćwiczenie: minimalne drzewo rozpinające z DSU
Algorytm Kruskala wyznaczania minimalnego drzewa rozpinającego bezpośrednio wykorzystuje DSU. Należy posortować wszystkie krawędzie według wag, a następnie zachłannie dodawać każdą krawędź, jeśli jej końce należą do różnych składowych (czyli nie tworzy ona cyklu). DSU zapewnia sprawdzanie cyklu w czasie bliskim O(1). Wynikiem jest MST z n-1 krawędziami.
To klasyczny przykład możliwości DSU: metoda zamienia naiwne sprawdzanie cyklu w czasie O(E × V) na proces o złożoności O(E × alpha(n)). Po sortowaniu w czasie O(E log E) całkowita złożoność czasowa algorytmu Kruskala wynosi O(E log E), a operacje DSU są tak szybkie, że ich koszt można pominąć w porównaniu z sortowaniem.
def kruskal(n, edges):
edges.sort(key=lambda e: e[2]) # sort by weight
parent = list(range(n))
rank = [0] * 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: return False
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
mst_weight = 0
mst_edges = []
for u, v, w in edges:
if union(u, v):
mst_weight += w
mst_edges.append((u, v, w))
return mst_weight, mst_edges
edges = [(0,1,4),(0,2,3),(1,2,1),(1,3,2),(2,3,5)]
w, e = kruskal(4, edges)
print('MST weight:', w) # 6: edges (1,2,1)+(1,3,2)+(0,2,3)
print('MST edges:', e)DSU z możliwością wycofywania: spójność offline
Standardowy DSU nie obsługuje operacji cofania. Istnieje jednak DSU z możliwością wycofywania (nazywany także DSU z historią): zamiast kompresji ścieżki (którą trudno cofnąć) stosuje się wyłącznie łączenie według rangi i zapisuje każdą operację union na stosie. Aby cofnąć operacje, należy zdjąć element ze stosu i przywrócić wartości parent oraz rank. Umożliwia to rozwiązywanie offline'owych problemów dynamicznej spójności, w których krawędzie mogą być dodawane i usuwane.
Choć jest to zaawansowany wariant, rzadko spotykany na standardowych rozmowach rekrutacyjnych, pokazuje on, że kluczowym niezmiennikiem jest łączenie według rangi, a nie kompresja ścieżki. Bez kompresji ścieżki każda operacja find ma złożoność O(log n), a operacje na stosie związane z wycofywaniem mają złożoność O(1), co daje łącznie O(log n) na operację zamiast O(alpha(n)).
class DSUWithRollback:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.history = [] # stack of (node, old_parent, node2, old_rank)
def find(self, x): # NO path compression (cannot undo)
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: return False
if self.rank[px] < self.rank[py]: px, py = py, px
# Record state before modifying
self.history.append((py, self.parent[py], px, self.rank[px]))
self.parent[py] = px
if self.rank[px] == self.rank[py]: self.rank[px] += 1
return True
def rollback(self):
py, old_par_py, px, old_rank_px = self.history.pop()
self.parent[py] = old_par_py
self.rank[px] = old_rank_px
dsu = DSUWithRollback(5)
dsu.union(0, 1); dsu.union(1, 2)
print('0 and 2 connected:', dsu.find(0) == dsu.find(2)) # True
dsu.rollback()
print('After rollback:', dsu.find(0) == dsu.find(2)) # FalseSzybki sprawdzian
Sprawdź swoją znajomość pojęć z kursu Data Structures & Algorithms — Coding Interview Prep omawianych w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: łączenie według rangi zawsze dołącza płytsze drzewo do głębszego, ranga zwiększa się tylko wtedy, gdy łączą się dwa drzewa o tej samej randze, dzięki czemu wysokość drzewa pozostaje rzędu O(log n), a połączenie kompresji ścieżki z łączeniem według rangi zapewnia zamortyzowany czas O(alpha(n)) — w praktyce stały. Następnie zastosujemy w pełni zoptymalizowany DSU do problemu redundant connection oraz wykrywania cykli w grafach.
Często zadawane pytania
Czy lekcja „Łączenie według rangi i ograniczenie odwrotną funkcją Ackermanna” jest bezpłatna?
Tak — pełny tekst „Łączenie według rangi i ograniczenie odwrotną funkcją Ackermanna” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Łączenie według rangi i ograniczenie odwrotną funkcją Ackermanna”?
Dodawać łączenie według rangi, aby utrzymywać płaską strukturę drzew, oraz rozumieć, dlaczego połączenie obu optymalizacji daje zamortyzowany czas O(alpha(n)), czyli w praktyce stały Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Łączenie według rangi i ograniczenie odwrotną funkcją Ackermanna”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- DSU z kompresją ścieżek
- Łączenie według rangi i ograniczenie odwrotną funkcją Ackermanna
- Nadmiarowa krawędź i wykrywanie cykli
- Scalanie kont i spójne składowe