డిస్జాయింట్-సెట్ (యూనియన్-ఫైండ్) నాన్-ఓవర్లాపింగ్ గ్రూపులుగా విభజించిన మూలకాలను ట్రాక్ చేస్తుంది మరియు "ఈ ఇద్దరు ఒకే గ్రూపులో ఉన్నారా?" మరియు "" అనే ప్రశ్నలకు లో సమాధానం ఇస్తుంది. మరియు ఉన్నప్పుడు, రెండు ఆపరేషన్లు లో నడుస్తాయి — ప్రభావంగా 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) |
యూనియన్-ఫైండ్ సమూహం మరియు కానెక్టివిటీ సమస్యలను పరిష్కరిస్తుంది, వేరే విధంగా పునరావృత్తమయ్యే O(n) గ్రాఫ్ ట్రావర్సల్లను అవసరం చేస్తుంది, వాటిని ప్రతి ప్రశ్నకు సుమారు O(1)కు సంపీడనం చేస్తుంది।
సెట్లను క్రమంగా విలీనం చేయాలి మరియు కానెక్టివిటీని పరీక్షించాల్సిన ప్రతిసారీ ఇది ఎలుకకు సరిపోయే సాధనం — సీనియర్-లెవల్ ఇంటర్వ్యూ విషయం.