[Pseudocode] Union By Rank and Find With Path Compression

UnionByRank-FindWithPathCompression.py

# Init
parent = dict()
rank = dict()

# Find With Path Compression
def find(node):

    nonlocal parent

    # Find/Update the parent of the node
    if parent[node] == node:
        return node

    parent[node] = find(parent[node])

    return parent[node]

# Union by Rank
def union(x,y):

    # Find parent of x and y
    parent_x = find(x)
    parent_y = find(y)

    # If they are not same, then create union,
    # else ignore as to avoid creating cylce.
    if parent_x != parent_y:

        # If rank of "parent of x" is greater than
        # or equal to rank of "parent of y", then
        # make parent of "parent of y" equal to
        # "parent of x". And increment the rank
        # of "parent of x" by 1, visa versa.
        if rank[parent_x] >= rank[parent_y]:
            parent[parent_y] = parent_x
            rank[parent_x] += 1
        else:
            parent[parent_x] = parent_y
            rank[parent_y] += 1

    return

#######################################################

# Init
n = len(nodes)
parent = [-1] * n
rank = [0] * n

# Find By Compression
def findByCompression(node):
    nonlocal parent
    if parent[node] == -1:
        return node
    parent[node] = findByCompression(parent[node])
    return parent[node]

# Union By Rank
def unionByRank(x,y) -> bool:
    nonlocal rank
    nonlocal parent
    parent_x = findByCompression(x)
    parent_y = findByCompression(y)
    if parent_x != parent_y:
        if rank[parent_x] >= rank[parent_y]:
            parent[parent_y] = parent_x
            rank[parent_x] += 1
        else:
            parent[parent_x] = parent_y
            rank[parent_y] += 1
        return True
    return False