एक विचलित-संच (union-find) घटकांचा ट्रॅक करतो जो गैर-अतिव्यापी गटांमध्ये विभाजित केले जातात आणि "या दोन समान गटात आहेत का?" आणि "" हे प्रश्न उत्तर देतात. आणि सह, दोन्ही ऑपरेशन मध्ये चालते — प्रभावीपणे O(1) (α हे व्यस्त अॅकरमन फंक्शन आहे).
एक विचलित-संच (union-find) घटकांचा ट्रॅक करतो जो गैर-अतिव्यापी गटांमध्ये विभाजित केले जातात आणि "या दोन समान गटात आहेत का?" आणि "" हे प्रश्न उत्तर देतात. आणि सह, दोन्ही ऑपरेशन मध्ये चालते — प्रभावीपणे O(1) (α हे व्यस्त अॅकरमन फंक्शन आहे).
प्रत्येक संच एक वृक्ष आहे; रूट हे संचाचे प्रतिनिधी आहे. 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) प्रति क्वेरीमध्ये संकुचित करते.
जेव्हा तुम्हाला संचांचे वाढीव विलीकरण करायचे असते आणि संयोजकता तपासायची असते — एक वारंवार सीनियर-स्तरीय मुलाखत विषय — तेव्हा ही एक जाणीव असलेली साधन आहे.