Union-find

Union-find merges disjoint sets.

Union-find tracks a graph's nodes in sets. find(x) locates x's root; union(x, y) merges two sets.

This structure is used in Kruskal's cycle check. Each node points to a parent; the root points to itself.

Parent array

Each node has a parent. Initially each node is its own parent: parent[i] = i. When merged, the parent is updated.

Finding the root follows the parent chain: while parent[x] != x: x = parent[x]. This loop continues until the root is found.

Write init_parent(n). Return a parent array where each node is its own parent. Print it with print(init_parent(4)).

Show example solution

def init_parent(n):
    # Return parent array
    return list(range(n))
print(init_parent(4))

Next lesson: Trie