Union-Find (Disjoint Set Union) तत्वहरूको एक विभाजनलाई disjoint sets मा ट्र्याक गर्छ र दुई लगभग-O(1) सञ्चालन समर्थन गर्छ: find (x कुन सेटमा छ?) र union (दुई सेट मर्ज गर्नुहोस्)। यो connectivity queries मा उत्कृष्ट छ।
प्रत्येक सेट एक प्रतिनिधि root भएको एक रुख हो। र को साथ, सञ्चालनहरू लगभग स्थिर समयमा चल्छन् (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
path compression र union by rank बिना, रुखहरू O(n) chains मा ह्रास हुन्छन्। यो सेटहरूको efficient splitting समर्थन गर्दैन।
Union-find "के यी दुई वस्तुहरू जोडिएका छन्?" को प्रश्नको उत्तर विशाल स्केलमा लगभग कुनै लागतमा दिन्छ।
यो Kruskal's MST र धेरै graph र clustering algorithms भित्रको इञ्जिन हो।
यसका दुई अनुकूलनहरू एक सम्झनयोग्य पाठ हुन् कि कसरी साना संरचनात्मक चालले लगभग-स्थिर-समय प्रदर्शन प्राप्त गर्छन्।