Here is my implementation of Union Find with Path Compression in Python.
class uf: def __init__(self,numnodes): self.r = [1] * (numnodes) self.p = [] for i in range(n): self.p.append(i) def j(self,a,b): if a == b: return a=self.root(a) b=self.root(b) if a == b: return if self.r[a] > self.r[b]: self.r[a]+=self.r[b] self.p[b]= self.p[a] else : self.r[b]+=self.r[a] self.p[a] = self.p[b] def root(self,a): while True: if self.p[a]==a: break else: self.p[a] =self.p[self.p[a]] a = self.p[a] return a def q(self,a,b): if self.root(a) == self.root(b): return True else: return False
Comments
Post a Comment