Union-Find (Disjoint Set Union) ਤੱਤਾਂ ਦੀ ਵੰਡ ਨੂੰ disjoint sets ਵਿੱਚ ਟਰੈਕ ਕਰਦਾ ਹੈ ਅਤੇ ਦੋ ਲਗਭਗ-O(1) operations ਨੂੰ ਸਪੋਰਟ ਕਰਦਾ ਹੈ: find (x ਕਿਸ set ਵਿੱਚ ਹੈ?) ਅਤੇ union (ਦੋ sets ਨੂੰ ਮਿਲਾਓ)। ਇਹ connectivity queries ਵਿੱਚ ਸ਼ਾਨਦਾਰ ਹੈ।
ਹਰੇਕ set ਇੱਕ ਪ੍ਰਤੀਨਿਧੀ root ਵਾਲਾ ਰੁੱਖ ਹੈ। ਅਤੇ ਦੇ ਨਾਲ, operations ਲਗਭਗ ਸਥਿਰ ਸਮੇਂ ਚਲਦੇ ਹਨ (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 ਵਿੱਚ ਖਰਾਬ ਹੋ ਜਾਂਦੇ ਹਨ। ਇਹ sets ਦੀ efficient splitting ਨੂੰ ਸਪੋਰਟ ਨਹੀਂ ਕਰਦਾ।
Union-find "ਕੀ ਇਹ ਦੋ ਚੀਜ਼ਾਂ ਸੰਯੁਕਤ ਹਨ?" ਦੇ ਉੱਤਰ ਲਈ ਬਹੁਤ ਵੱਡੇ ਪੈਮਾਨੇ 'ਤੇ ਲਗਭਗ ਕੋਈ ਲਾਗਤ ਨਾਲ।
ਇਹ Kruskal's MST ਅਤੇ ਬਹੁਤ ਸਾਰੀ graph ਅਤੇ clustering algorithms ਦੇ ਅੰਦਰ ਇੰਜਨ ਹੈ।
ਇਸ ਦੀ ਦੋ optimizations ਇਸ ਦਾ ਯਾਦ ਰਹਿਣ ਵਾਲਾ ਸਬਕ ਹਨ ਕਿ ਛੋਟੀ structural tricks ਕਿਵੇਂ ਲਗਭਗ constant-time performance ਦਿੰਦੀਆਂ ਹਨ।