Union-Find (Disjoint Set Union - Tập hợp rời rạc) theo dõi một phân hoạch các phần tử thành các tập rời nhau (disjoint sets) và hỗ trợ hai thao tác gần như O(1): find (x thuộc tập nào?) và union (gộp hai tập). Nó xuất sắc với các truy vấn về tính liên thông.
Mỗi tập là một cây với một gốc đại diện. Với (nén đường) và (gộp theo hạng/kích thước), các thao tác chạy trong thời gian gần như hằng số (Ackermann nghịch đảo, α(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]] # nén
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # đã liên thông
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # gắn cây nhỏ hơn dưới cây lớn hơn
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
Không có path compression và union by rank, các cây thoái hóa thành các chuỗi O(n). Nó không hỗ trợ tách (splitting) các tập một cách hiệu quả.
Union-find trả lời "hai thứ này có liên thông không?" ở quy mô khổng lồ với gần như không tốn chi phí.
Nó là động cơ bên trong MST của Kruskal và nhiều thuật toán đồ thị và phân cụm.
Hai tối ưu hóa của nó là một bài học đáng nhớ về việc những mẹo cấu trúc nhỏ tạo ra hiệu năng gần như thời gian hằng số.