Time complexity

• O(n log(n))
• Traversing through a tree, the join operation just link the two root nodes

inverse ackermann function

par = [i for i in range(numNodes + 1)]
rank = [1] * (numNodes + 1)


def find(src):
    parent = par[src]

    while parent != par[parent]:
        par[parent] = par[par[parent]]
        parent = par[parent]

    return parent


def union(s1, s2):
    p1, p2 = find(s1), find(s2)

    if p1 == p2:
        return False

    if rank[p1] > rank[p2]:
        par[p2] = p1
        rank[p1] += rank[p2]
    else:
        par[p1] = p2
        rank[p2] += rank[p1]

    return True