# Path: unionfind/quickfind.py
# class QuickFind(UnionFind):
# 
#     def __init__(self, n):
#         UnionFind.__init__(self, n)
# 
#     def parent(self, index):
#         return self.arr[index]
# 
#     def connect(self, item1, item2):
#         pid1 = self.arr[item1]
#         pid2 = self.arr[item2]
# 
#         for i in xrange(self.n):
#             if self.arr[i] == pid2:
#                 self.arr[i] = pid1
# 
# Path: unionfind/quickunion.py
# class QuickUnion(UnionFind):
# 
#     def __init__(self, n):
#         UnionFind.__init__(self, n)
# 
#     def connect(self, item1, item2):
#         pid1 = self.parent(item1)
#         pid2 = self.parent(item2)
#         self.arr[pid2] = pid1
# 
#     def parent(self, index):
#         current_item = index
#         while self.arr[current_item] != current_item:
#             current_item = self.arr[current_item]
# 
#         return current_item
# 
# Path: unionfind/weightedquickunion.py
# class WeightedQuickUnion(QuickUnion):
# 
#     def __init__(self, n):
#         QuickUnion.__init__(self, n)
#         self.item_counts = [1] * n
# 
#     def connect(self, item1, item2):
#         pid1 = self.parent(item1)
#         pid2 = self.parent(item2)
#         if self.item_counts[pid1] > self.item_counts[pid2]:
#             self.arr[pid2] = pid1
#             self.item_counts[pid1] += self.item_counts[pid2]
#         else:
#             self.arr[pid1] = pid2
#             self.item_counts[pid2] += self.item_counts[pid1]
# 
# Path: unionfind/wquwithpathcompression.py
# class WQUWithPathCompression(WeightedQuickUnion):
# 
#     def __init__(self, n):
#         WeightedQuickUnion.__init__(self, n)
# 
#     def parent(self, index):
#         current_item = index
#         while self.arr[current_item] != current_item:
#             current_item = self.arr[current_item]
# 
#         update_index = index
#         while self.arr[update_index] != current_item:
#             parent_index = self.arr[update_index]
#             self.arr[update_index] = current_item
#             update_index = parent_index
# 
#         return current_item


from unittest import TestCase
from unionfind.quickfind import QuickFind
from unionfind.quickunion import QuickUnion
from unionfind.weightedquickunion import WeightedQuickUnion
from unionfind.wquwithpathcompression import WQUWithPathCompression
        self.algorithm.connect(1, 2)
        self.algorithm.connect(3, 4)
        self.assertTrue(not self.algorithm.isConnected(2, 3))
        self.algorithm.connect(1, 4)
        self.assertTrue(self.algorithm.isConnected(2, 3))
        self.assertTrue(self.algorithm.isConnected(2, 4))
        self.assertTrue(not self.algorithm.isConnected(2, 9))


class QuickFindTests(UnionFindTests, TestCase):

    def setUp(self):
        self.algorithm = QuickFind(100)


class QuickUnionTests(UnionFindTests, TestCase):

    def setUp(self):
        self.algorithm = QuickUnion(100)


class WeightedQuickUnionTests(UnionFindTests, TestCase):

    def setUp(self):
        self.algorithm = WeightedQuickUnion(100)


class WQUWithPathCompressionTests(UnionFindTests, TestCase):

    def setUp(self):

# Path: unionfind/quickfind.py
# class QuickFind(UnionFind):
# 
#     def __init__(self, n):
#         UnionFind.__init__(self, n)
# 
#     def parent(self, index):
#         return self.arr[index]
# 
#     def connect(self, item1, item2):
#         pid1 = self.arr[item1]
#         pid2 = self.arr[item2]
# 
#         for i in xrange(self.n):
#             if self.arr[i] == pid2:
#                 self.arr[i] = pid1
# 
# Path: unionfind/quickunion.py
# class QuickUnion(UnionFind):
# 
#     def __init__(self, n):
#         UnionFind.__init__(self, n)
# 
#     def connect(self, item1, item2):
#         pid1 = self.parent(item1)
#         pid2 = self.parent(item2)
#         self.arr[pid2] = pid1
# 
#     def parent(self, index):
#         current_item = index
#         while self.arr[current_item] != current_item:
#             current_item = self.arr[current_item]
# 
#         return current_item
# 
# Path: unionfind/weightedquickunion.py
# class WeightedQuickUnion(QuickUnion):
# 
#     def __init__(self, n):
#         QuickUnion.__init__(self, n)
#         self.item_counts = [1] * n
# 
#     def connect(self, item1, item2):
#         pid1 = self.parent(item1)
#         pid2 = self.parent(item2)
#         if self.item_counts[pid1] > self.item_counts[pid2]:
#             self.arr[pid2] = pid1
#             self.item_counts[pid1] += self.item_counts[pid2]
#         else:
#             self.arr[pid1] = pid2
#             self.item_counts[pid2] += self.item_counts[pid1]
# 
# Path: unionfind/wquwithpathcompression.py
# class WQUWithPathCompression(WeightedQuickUnion):
# 
#     def __init__(self, n):
#         WeightedQuickUnion.__init__(self, n)
# 
#     def parent(self, index):
#         current_item = index
#         while self.arr[current_item] != current_item:
#             current_item = self.arr[current_item]
# 
#         update_index = index
#         while self.arr[update_index] != current_item:
#             parent_index = self.arr[update_index]
#             self.arr[update_index] = current_item
#             update_index = parent_index
# 
#         return current_item


# Path: tests/unionfind/unionfind_test.py
from unittest import TestCase
from unionfind.quickfind import QuickFind
from unionfind.quickunion import QuickUnion
from unionfind.weightedquickunion import WeightedQuickUnion
from unionfind.wquwithpathcompression import WQUWithPathCompression

        self.algorithm.connect(1, 2)
        self.algorithm.connect(3, 4)
        self.assertTrue(not self.algorithm.isConnected(2, 3))
        self.algorithm.connect(1, 4)
        self.assertTrue(self.algorithm.isConnected(2, 3))
        self.assertTrue(self.algorithm.isConnected(2, 4))
        self.assertTrue(not self.algorithm.isConnected(2, 9))


class QuickFindTests(UnionFindTests, TestCase):

    def setUp(self):
        self.algorithm = QuickFind(100)


class QuickUnionTests(UnionFindTests, TestCase):

    def setUp(self):
        self.algorithm = QuickUnion(100)


class WeightedQuickUnionTests(UnionFindTests, TestCase):

    def setUp(self):
        self.algorithm = WeightedQuickUnion(100)


class WQUWithPathCompressionTests(UnionFindTests, TestCase):

    def setUp(self):

        self.algorithm = WQUWithPathCompression(100)