Union Berdasarkan Rank dan Batas Invers Ackermann
Tambahkan union berdasarkan rank untuk menjaga pohon tetap datar, lalu pahami mengapa optimasi gabungan menghasilkan waktu amortisasi O(alpha(n)), yang secara efektif konstan
Union Berdasarkan Rank dan Batas Invers Ackermann adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Mengapa Pohon Menjadi Tinggi Tanpa Peringkat
Kompresi jalur biasa mencegah pohon menjadi tinggi setelah penelusuran, tetapi selama operasi union awal, kita masih dapat membangun pohon yang tinggi jika selalu menautkan akar pohon yang lebih besar di bawah akar pohon yang lebih kecil. Union berdasarkan peringkat mengatasi hal ini dengan melacak batas atas tinggi pohon (peringkat) dan selalu menautkan pohon yang lebih dangkal di bawah pohon yang lebih dalam.
Peringkat tidak persis sama dengan tinggi — kompresi jalur dapat mengurangi tinggi hingga di bawah peringkat — tetapi merupakan batas atas. Dengan mempertahankan pohon yang lebih dalam sebagai akar baru, kita memastikan peringkat hanya meningkat ketika dua pohon dengan peringkat sama digabungkan, sehingga membatasi peringkat maksimum hingga 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 TrueTiga Kasus Union Berdasarkan Peringkat
Saat menggabungkan dua komponen dengan akar px dan py, terdapat tiga kasus berdasarkan peringkatnya:
- peringkat[px] > peringkat[py]: tautkan py di bawah px — peringkat px tidak berubah
- peringkat[px] < peringkat[py]: tautkan px di bawah py — peringkat py tidak berubah
- peringkat[px] == peringkat[py]: tautkan py di bawah px (atau sebaliknya) — peringkat akar baru meningkat sebesar 1
Peringkat hanya bertambah pada kasus dengan peringkat yang sama. Ini berarti peringkat n memerlukan setidaknya 2^n simpul, sehingga peringkat maksimum adalah O(log n). Hal ini menjaga jalur find tetap pendek bahkan tanpa kompresi jalur.
# 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))Gabungan Kompresi Jalur + Union Berdasarkan Peringkat
Ketika kompresi jalur dan union berdasarkan peringkat digunakan bersama, waktu diamortisasi per operasi turun menjadi O(alpha(n)) — fungsi invers Ackermann. Untuk ukuran masukan praktis apa pun (hingga 2^65536), alpha(n) paling tinggi adalah 4. Ini secara efektif merupakan waktu konstan.
Kompresi jalur meratakan pohon dari bawah ke atas setelah penelusuran, sedangkan union berdasarkan peringkat mencegah pohon tumbuh tinggi dari atas ke bawah selama penggabungan. Keduanya saling melengkapi: peringkat membatasi kedalaman awal, dan kompresi menghilangkan kedalaman tersebut setelah penelusuran pertama.
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 smallMemahami Fungsi Invers Ackermann
Fungsi Ackermann A(m, n) tumbuh luar biasa cepat — lebih cepat daripada fungsi rekursif primitif apa pun. Inversnya, alpha(n), didefinisikan sebagai m terkecil sedemikian rupa sehingga A(m, m) >= n. Karena fungsi Ackermann tumbuh sangat cepat, alpha(n) tumbuh sangat lambat hingga sulit dibayangkan.
Untuk n = 10^80 (jumlah atom di alam semesta yang dapat diamati), alpha(n) tetap hanya 4. Inilah sebabnya DSU dengan kedua optimisasi diperlakukan sebagai waktu yang secara efektif konstan dalam setiap situasi praktis. Anda tidak akan pernah menemui masalah nyata yang cukup besar sehingga alpha(n) melebihi 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.')Peringkat vs Ukuran: Mana yang Digunakan
Alternatif untuk union berdasarkan peringkat adalah union berdasarkan ukuran: selalu tautkan pohon dengan ukuran lebih kecil di bawah pohon dengan ukuran lebih besar. Kedua pendekatan memberikan jaminan tinggi O(log n) yang sama. Union berdasarkan ukuran sering kali lebih mudah dipahami karena ukurannya merupakan hitungan yang tepat, sedangkan peringkat adalah batas atas yang mungkin tidak mencerminkan tinggi sebenarnya setelah kompresi.
Dalam wawancara, pendekatan mana pun dapat diterima. Union berdasarkan ukuran memiliki manfaat tambahan berupa ukuran komponen tanpa biaya tambahan, yang dibutuhkan banyak masalah. Union berdasarkan peringkat sedikit lebih elegan secara teoretis dan sesuai dengan pembuktian Tarjan asli mengenai batas invers Ackermann.
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)])Sketsa Pembuktian: Mengapa Peringkat Tetap O(log n)
Kita dapat membuktikan dengan induksi bahwa pohon DSU dengan peringkat r memiliki setidaknya 2^r simpul. Kasus dasar: peringkat 0 berarti satu simpul (2^0 = 1). Langkah induksi: peringkat r hanya meningkat ketika dua pohon dengan peringkat r-1 yang sama digabungkan. Berdasarkan hipotesis induksi, setiap subpohon memiliki setidaknya 2^(r-1) simpul, sehingga pohon gabungan memiliki setidaknya 2 × 2^(r-1) = 2^r simpul.
Karena pohon dengan peringkat r memiliki setidaknya 2^r simpul, sedangkan jumlah seluruh simpul adalah n, peringkat maksimum paling besar log₂(n). Ini berarti find tanpa kompresi jalur memerlukan waktu O(log n), dan dengan kompresi jalur biaya diamortisasinya turun jauh lebih rendah.
# 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}')Templat DSU untuk Pemrograman Kompetitif
Dalam pemrograman kompetitif dan wawancara, Anda menginginkan templat DSU yang telah teruji, singkat, benar, dan menangani semua kasus tepi. Templat di bawah menggunakan pembagian jalur menjadi dua (kompresi satu lintasan) yang digabungkan dengan union berdasarkan ukuran — kombinasi yang mudah diketik dengan cepat dan sepenuhnya menghindari rekursi.
Selalu inisialisasi parent[i] = i dan size[i] = 1. Ingat bahwa setelah find, size akar mencerminkan seluruh komponen. Jangan pernah menggunakan size[x] secara langsung — selalu panggil 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)) # 3Saat DSU Tidak Cukup
DSU mendukung penggabungan himpunan, tetapi tidak mendukung pemisahan suatu himpunan kembali menjadi dua. Jika masalah memerlukan penggabungan dan pemisahan kelompok, Anda memerlukan struktur berbeda (seperti pohon taut-potong). DSU juga tidak secara bawaan menyimpan elemen setiap kelompok — Anda memerlukan daftar ketetanggaan atau kamus tambahan untuk itu.
Selain itu, DSU standar tidak mendukung sisi berbobot tanpa modifikasi (DSU berbobot adalah varian yang lebih lanjut). Untuk masalah seperti mencari jalur termurah antara simpul yang connected, Dijkstra atau BFS lebih sesuai. Memahami cakupan DSU mencegah Anda menerapkannya secara keliru.
# 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] = pxMembandingkan DSU dengan BFS/DFS untuk Konektivitas
BFS/DFS dan DSU sama-sama menyelesaikan kueri konektivitas statis, tetapi keduanya memiliki keunggulan yang berbeda. BFS/DFS berjalan dalam O(V + E) dan dapat menemukan jalur sebenarnya antara simpul. DSU menjawab banyak kueri konektivitas pada kumpulan sisi yang terus bertambah dengan waktu mendekati O(1) per kueri — ideal untuk algoritme daring, yaitu saat sisi datang satu per satu.
Jika Anda menerima semua sisi sejak awal dan hanya memerlukan konektivitas, keduanya dapat digunakan. Jika sisi datang secara dinamis dan Anda perlu menjawab kueri konektivitas setiap kali sisi baru ditambahkan, DSU jelas lebih unggul. Untuk masalah yang juga memerlukan jalur terpendek, gunakan 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.')Latihan: Pohon Merentang Minimum dengan DSU
Algoritme Kruskal untuk pohon merentang minimum menggunakan DSU secara langsung. Pertama, lakukan sort terhadap semua sisi berdasarkan bobot, lalu tambahkan setiap sisi secara bertahap jika titik ujungnya berada di komponen yang berbeda (tanpa siklus). DSU menyediakan pemeriksaan siklus dalam waktu mendekati O(1). Hasilnya adalah sebuah MST dengan n-1 sisi.
Ini adalah demonstrasi klasik tentang keunggulan DSU: DSU mengubah pemeriksaan siklus naif O(E × V) menjadi proses O(E × alpha(n)). Dengan sort dalam waktu E log E, total waktu Kruskal adalah O(E log E), dan operasi DSU sangat cepat sehingga biayanya dapat diabaikan dibandingkan sort.
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 dengan Rollback: Konektivitas Luring
DSU standar tidak mendukung operasi pembatalan. Namun, DSU dengan rollback (juga disebut DSU dengan riwayat) mendukungnya: alih-alih menggunakan kompresi jalur (yang sulit dibatalkan), gunakan hanya union berdasarkan peringkat, lalu catat setiap operasi union dalam sebuah tumpukan. Untuk melakukan rollback, lakukan pop dari tumpukan dan pulihkan induk serta peringkatnya. Hal ini memungkinkan penyelesaian masalah konektivitas dinamis luring, ketika sisi dapat ditambahkan dan dihapus.
Walaupun varian ini tergolong tingkat lanjut dan jarang muncul dalam wawancara standar, varian ini menunjukkan bahwa union berdasarkan peringkat adalah invarian yang penting — bukan kompresi jalur. Tanpa kompresi jalur, setiap operasi find membutuhkan O(log n), sedangkan dengan rollback, operasi tumpukan membutuhkan O(1), sehingga totalnya menjadi O(log n) per operasi, bukan 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)) # FalsePemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari bahwa: union berdasarkan peringkat selalu menempatkan pohon yang lebih dangkal di bawah pohon yang lebih dalam, peringkat hanya bertambah ketika dua pohon dengan peringkat yang sama digabungkan, sehingga tinggi pohon tetap O(log n), dan penggabungan kompresi jalur dengan union berdasarkan peringkat menghasilkan O(alpha(n)) secara diamortisasi — secara efektif waktu konstan. Selanjutnya, kita akan menerapkan DSU optimal secara lengkap pada masalah koneksi redundan dan deteksi siklus dalam graf.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Union Berdasarkan Rank dan Batas Invers Ackermann” gratis?
Ya — teks lengkap “Union Berdasarkan Rank dan Batas Invers Ackermann” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Union Berdasarkan Rank dan Batas Invers Ackermann”?
Tambahkan union berdasarkan rank untuk menjaga pohon tetap datar, lalu pahami mengapa optimasi gabungan menghasilkan waktu amortisasi O(alpha(n)), yang secara efektif konstan Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Union Berdasarkan Rank dan Batas Invers Ackermann” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- DSU dengan Kompresi Jalur
- Union Berdasarkan Rank dan Batas Invers Ackermann
- Koneksi Berlebih dan Deteksi Siklus
- Penggabungan Akun dan Komponen Terhubung