Union-Find (Disjoint Set Union) உறுப்புகளின் பிভাகியலை விலகிய தொகுப்புகளாக பதிவு செய்து இரண்டு கிட்டத்தட்ட O(1) செயல்பாடுகளை ஆதரிக்கிறது: find (x எந்த தொகுப்பில் உள்ளது?) மற்றும் union (இரண்டு தொகுப்புகளை ஒன்றிணைக்கவும்). இது இணைப்பு வினாக்களுக்குக் சிறந்ததாக உள்ளது.
ஒவ்வொரு தொகுப்பும் பிரதிநிதி வேர் கொண்ட ஒரு மரம். மற்றும் உடன், செயல்பாடுகள் கிட்டத்தட்ட மாறிலி நேரத்தில் இயங்குகின்றன (inverse 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
பாத் சுருக்கம் மற்றும் வரிசை/அளவு ஒன்றியல் இல்லாமல், மரங்கள் O(n) சங்கிலிகளாக தேய்கின்றன. இது தொகுப்புகளின் திறமையான பிভாகத்தை ஆதரிக்காது.
Union-find "இந்த இரண்டு விஷயங்களும் இணைக்கப்பட்டுள்ளனவா?" என்ற கேள்விக்கு பெரும் அளவில் கிட்டத்தட்ட எந்த செலவுமின்றி பதிலளிக்கிறது.
இது Kruskalன் MST மற்றும் பல வரைபடம் மற்றும் க्लस्टरिং வழிமுறைகளின் உள்ளே என்जिन ஆகும்.
அதன் இரண்டு மேம்படுத்தல்கள் சிறிய கட்ட தந்திரங்கள் கிட்டத்தட்ட மாறிலி-நேர செயல்திறனை எவ்வாறு ஏற்படுத்துகிறது என்பதற்கான நினைவக பாடமாகும்.