20241016 ◎

def find_parent(i: int, parent: list[int]) -> int:
    if parent[parent[i]] != parent[i]:
        pareit[i] = find_parent(parent[i], parent)
    return parent[i]


def union_nodes(a: int, b: int, parent: list[int], size: list[int]) -> None:
    parent_a: int = find_parent(a, parent)
    parent_b: int = find_parent(b, parent)

    if parent_a == parent_b:
        return

    if size[parent_a] >= size[parent_b]:
        size[parent_a] += size[parent_b]
        parent[parent_b] = parent_a
    else:
        size[parent_b] += size[parent_a]
        parent[parent_a] = parent_b


if __name__ == "__main__":
    n = 10  # num of nodes
    m = 7  # num of edges
    edges = [
        (0, 1),
        (0, 2),
        (1, 2),
        (3, 4),
        (5, 2),
        (6, 7),
        (7, 8),
    ]

    parent: list[int] = list(range(n))
    size: list[int] = [1] * n

    for a, b in edges:
        union_nodes(a, b, parent, size)

    # some finding parents are postponed to save calculations
    for i in range(n):
        find_parent(i, parent)

    # count the leaders
    num_components: int = 0
    for i in range(n):
        if find_parent(i, parent) == i:
            num_components += 1

    print(f"{parent=}")  # [0, 0, 0, 3, 3, 0, 6, 6, 6, 9]
    print(f"{size=}")  # [4, 1, 1, 2, 1, 1, 3, 1, 1, 1]
    print(f"{num_components=}")  # 4