2. Disjoint Set Union Find Optimized

Disjoint Set or Union Find optimized implementation¶

References:¶

1. https://www.techiedelight.com/disjoint-set-data-structure-union-find-algorithm/
2. Explanation: https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/
3. Algorithm implementation in Python: https://www.geeksforgeeks.org/disjoint-set-data-structures/

In [1]:

class DisjointSetOptimized:
    def __init__(self):
        self.parent = {}
        self.rank = {}

    def make_set(self, universe):
        for i in universe:
            self.parent[i] = i
            self.rank[i] = 0

    def find(self, k):
        if self.parent[k] == k:
            return self.parent[k]

        else:
            root = self.find(self.parent[k])
            self.parent[k] = root
            return root

    def union(self, x, y):

        x_root = self.find(x)
        y_root = self.find(y)

        if x_root == y_root:
            return

        if self.rank[x_root] > self.rank[y_root]:
            self.parent[y_root] = x_root
        elif self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[x_root] = y_root
            self.rank[y_root] += 1

    def print_sets(self, universe):
        print(self.parent)
        print([self.find(i) for i in universe])

class DisjointSetOptimized: def __init__(self): self.parent = {} self.rank = {} def make_set(self, universe): for i in universe: self.parent[i] = i self.rank[i] = 0 def find(self, k): if self.parent[k] == k: return self.parent[k] else: root = self.find(self.parent[k]) self.parent[k] = root return root def union(self, x, y): x_root = self.find(x) y_root = self.find(y) if x_root == y_root: return if self.rank[x_root] > self.rank[y_root]: self.parent[y_root] = x_root elif self.rank[x_root] < self.rank[y_root]: self.parent[x_root] = y_root else: self.parent[x_root] = y_root self.rank[y_root] += 1 def print_sets(self, universe): print(self.parent) print([self.find(i) for i in universe])

In [2]:

if __name__ == "__main__":

    universe = [1, 2, 3, 4, 5]

    ds = DisjointSetOptimized()

    ds.make_set(universe)
    ds.print_sets(universe)

    ds.union(4, 3)
    ds.print_sets(universe)

    ds.union(4, 5)
    ds.print_sets(universe)

if __name__ == "__main__": universe = [1, 2, 3, 4, 5] ds = DisjointSetOptimized() ds.make_set(universe) ds.print_sets(universe) ds.union(4, 3) ds.print_sets(universe) ds.union(4, 5) ds.print_sets(universe)

{1: 1, 2: 2, 3: 3, 4: 4, 5: 5}
[1, 2, 3, 4, 5]
{1: 1, 2: 2, 3: 3, 4: 3, 5: 5}
[1, 2, 3, 3, 5]
{1: 1, 2: 2, 3: 3, 4: 3, 5: 3}
[1, 2, 3, 3, 3]