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