एक डिसजॉइंट-सेट (union-find) तत्वों को गैर-अतिव्यापी समूहों में विभाजित करता है और "क्या ये दोनों एक ही समूह में हैं?" और "" को में उत्तर देता है। और के साथ, दोनों ऑपरेशन में चलते हैं — प्रभावी रूप से O(1) (α inverse Ackermann फंक्शन है)।
एक डिसजॉइंट-सेट (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) |
Union-find समूहीकरण और कनेक्टिविटी समस्याओं को हल करता है जिन्हें अन्यथा दोहराए गए O(n) ग्राफ ट्रैवर्सल की आवश्यकता होती, उन्हें लगभग O(1) प्रति क्वेरी तक घटाकर।
यह एक आवश्यक उपकरण है जब भी आपको सेट को क्रमिक रूप से मर्ज करना हो और कनेक्टिविटी का परीक्षण करना हो — एक बार-बार senior-level साक्षात्कार विषय।
विस्तृत उत्तरों के साथ IT इंटरव्यू प्रश्नों की एक लाइब्रेरी — जूनियर से सीनियर तक।
दान करें