classdforest(object):"""union-find with union-by-rank and path compression"""def__init__(self,cap=100):"""creates a disjoint forest with the given capacity"""self.__parent=[iforiinrange(cap)]self.__rank=[0foriinrange(cap)]self.__ccount=capdef__str__(self):"""return the string representation of the disjoint forest"""returnstr(self.__parent)def__len__(self):"""return the length of the disjoint forest"""returnlen(self.__parent)deffind(self,x):"""return the representative of x in the disjoint forest"""ans=self.__parent[x]ifans!=x:self.__parent[x]=ans=self.find(ans)returnansdefunion(self,x,y):"""union of the trees of x and y"""rx,ry=self.find(x),self.find(y)ifrx!=ry:kx,ky=self.__rank[rx],self.__rank[ry]ifkx>=ky:self.__parent[ry]=rxifkx==ky:self.__rank[rx]+=1else:self.__parent[rx]=ryself.__ccount-=1defccount(self):"""return the number of trees in the dijoint forest"""returnself.__ccount
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.