एक disjoint-set (union-find) गैर-अतिव्यापी समूहमा विभाजित गरिएका तत्वहरूलाई ट्र्याक गर्दछ र "के यी दुई एउटै समूहमा छन्?" र "" को प्रश्नको जवाफ मा दिन्छ। र सहित, दुबै अपरेसनहरू मा चल्छन् — प्रभावकारी रूपमा O(1) (α inverse Ackermann फंक्शन हो)।
एक disjoint-set (union-find) गैर-अतिव्यापी समूहमा विभाजित गरिएका तत्वहरूलाई ट्र्याक गर्दछ र "के यी दुई एउटै समूहमा छन्?" र "" को प्रश्नको जवाफ मा दिन्छ। र सहित, दुबै अपरेसनहरू मा चल्छन् — प्रभावकारी रूपमा O(1) (α inverse Ackermann फंक्शन हो)।
प्रत्येक सेट एक रूख हो; रूट सेटको प्रतिनिधि हो। find रूटमा हिँड्छ; union एक रूटलाई अर्कोको मुनि जोड्छ।
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
before: a->b->c->root after: a->root, b->root, c->root
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0]*n
def find(self, x): # path compression
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # halve path
x = self.parent[x]
return x
def union(self, a, b): # union by rank
ra, rb = self.find(a), self.find(b)
if ra == rb: return False
if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
return True
| अपरेसन | समय (दुबै अप्टिमाइजेशनसहित) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |
यूनियन-फाइन्डले समूहन र जोडिएकता समस्याहरू समाधान गर्दछ जसलाई अन्यथा दोहोरिएको O(n) ग्राफ ट्रैभर्सलको आवश्यकता पर्दो, तिनीहरूलाई लगभग O(1) प्रति क्वेरीमा पतन गराएर।
जब पनि तपाइँले क्रमशः सेटहरू मर्ज गर्नु पर्छ र जोडिएकता परीक्षण गर्नु पर्छ त्यसलाई यो एक जानु-पहचानु साधन हो — एक बारम्बार वरिष्ठ-स्तरको अन्तर्वार्ता विषय।