Union-Find (Disjoint Set Union) menjejakkan partisi elemen ke dalam set terpisah dan mendukung dua operasi hampir-O(1): find (x berada di set mana?) dan union (gabung dua set). Ia unggul dalam pertanyaan konektivitas.
Setiap set adalah pohon dengan akar perwakilan. Dengan dan , operasi berjalan dalam waktu hampir konstan (kebalikan Ackermann, α(n)).
class UnionFind:
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]] # compress
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already connected
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # attach smaller under larger
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
Tanpa kompresi jalur dan gabung menurut pangkat/ukuran, pohon merosot menjadi rantai O(n). Tidak mendukung pemisahan set yang efisien.
Union-find menjawab "apakah kedua hal ini terhubung?" dalam skala besar dengan biaya hampir nol.
Ini adalah mesin di dalam MST Kruskal dan banyak algoritma graf dan pengelompokan.
Dua optimisasi ini adalah pelajaran yang berkesan tentang bagaimana trik struktural kecil menghasilkan kinerja waktu hampir konstan.
Pustaka soalan temu duga IT dengan jawapan terperinci — daripada Junior hingga Senior.
Derma