Disjoint Set Union to maintain connectivity, Kruskal MST, and offline queries
Union by rank and path compression achieve near-constant-time connectivity operations.
Use for dynamic connectivity, grouping by relations, and Kruskal's MST.
Path compression and union-by-rank/size form near-constant-time DSU operations; use with Kruskal's MST and connectivity queries.
# Union-Find (Disjoint Set Union) Template
class DSU:
def __init__(self, n):
self.p=list(range(n)); self.r=[0]*n
def find(self, x):
if self.p[x]!=x: self.p[x]=self.find(self.p[x])
return self.p[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra==rb: return False
if self.r[ra]<self.r[rb]: ra,rb = rb,ra
self.p[rb]=ra
if self.r[ra]==self.r[rb]: self.r[ra]+=1
return TrueUnion and find with compression
class DSU:
def __init__(self, n): self.p=list(range(n)); self.r=[0]*n
def find(self, x):
if self.p[x]!=x: self.p[x]=self.find(self.p[x])
return self.p[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra==rb: return False
if self.r[ra]<self.r[rb]: ra,rb=rb,ra
self.p[rb]=ra
if self.r[ra]==self.r[rb]: self.r[ra]+=1
return TrueSort edges and union if not connected
def kruskal(n, edges):
# edges: (w,u,v)
dsu=DSU(n); edges.sort()
cost=0; mst=[]
for w,u,v in edges:
if dsu.union(u,v): cost+=w; mst.append((u,v,w))
return cost, mstProcess queries/events with DSU
# Example: offline union queries sorted by edge weight (simplified placeholder)
def offline_connectivity(n, edges, queries):
# edges: (w,u,v) sorted, queries: (w,u,v,idx) max weight allowed
dsu=DSU(n); i=0; ans=[False]*len(queries)
for w,u,v,idx in sorted(queries):
while i<len(edges) and edges[i][0]<=w:
_,a,b=edges[i]; dsu.union(a,b); i+=1
ans[idx]= (dsu.find(u)==dsu.find(v))
return ansInverse Ackermann per op.
Parents/rank arrays.