for testing and deploying your application
for finding and fixing issues
for empowering human code reviews
from abc import ABCMeta, abstractmethod
class UnionFind(object):
__metaclass__ = ABCMeta
@abstractmethod
def union(self, v, w):
pass
def connected(self, v, w):
@staticmethod
def create(size):
return QuickUnion(size)
class QuickFind(UnionFind):
id = None
def __init__(self, capacity):
self.id = [i for i in range(capacity)]
return self.id[v] == self.id[w]
p = self.id[v]
q = self.id[w]
if p != q:
for i in range(len(self.id)):
if self.id[i] == p:
self.id[i] = q
class QuickUnion(UnionFind):
sizes = None
self.sizes = [1] * capacity
def root(self, v):
while v != self.id[v]:
self.id[v] = self.id[self.id[v]] # path compression
v = self.id[v]
return v
return self.root(v) == self.root(w)
vroot = self.root(v)
wroot = self.root(w)
if self.sizes[vroot] > self.sizes[wroot]:
self.id[wroot] = vroot
self.sizes[vroot] += self.sizes[wroot]
else:
self.id[vroot] = wroot
self.sizes[wroot] += self.sizes[vroot]
chen0040 /
pyalgs
