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 మరియు అనేక గ్రాఫ్ మరియు క్లస్టరింగ్ అల్గారిథమ్ల లోపల ఇంజిన్.
ఇది యొక్క రెండు ఆప్టిమైజేషన్లు చిన్న నిర్మాణ ట్రిక్లు దాదాపు స్థిరమైన-సమయ పనితీరును ఎలా అందించాయి అనే విషయంలో స్మరణీయ పాఠం.