Algorithm_Implementations/QuickUnion.py at main · daijingz/Algorithm_Implementations · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# Author: Jingze Dai
# Email Address: [email protected] or [email protected]
# Github: https://github.com/daijingz
# Linkedin: https://www.linkedin.com/in/jingze-dai/
# Description: Quick Union


class QuickUnion:
    def __init__(self, n):
        """! QuickUnion object constructor """
        self.__groups = n
        self.__points = [x for x in range(n)]

    def get_groups(self):
        """! Getting objects' groups value """
        try:
            return self.__groups
        except:
            raise Exception()

    def get_points(self):
        """! Getting objects' points value """
        try:
            return self.__points
        except:
            raise Exception()

    def is_connected(self, p, q):
        """! Check 2 parts of an object about whether they are connected or not """
        try:
            return self.find(p) == self.find(q)
        except:
            raise Exception()

    def find(self, p):
        """! Find method """
        while p != self.__points[p]:
            p = self.__points[p]
        return p

    def union(self, p, q):
        """! Union method """
        parent = self.find(p)
        child = self.find(q)
        if parent == child:
            return

        self.__groups -= 1
        self.__points[child] = parent

    def __str__(self):
        """! Return the string form of object """
        return "groups: {0}; points: {1}".format(self.__groups, self.__points)

    def __repr__(self):
        """! Return a printable representation of object """
        return str(self)

    def __eq__(self, other):
        """! Check 2 objects on whether they are equal """
        if isinstance(other, QuickUnion):
            if self.__points == other.__points and self.__groups == other.__groups:
                return True
        return False