Summary - Advanced structures

Print union-find set merges in a mini task.

Summary - Advanced structures

In this group you learned three advanced structures: union-find, trie and segment tree. Each serves a different purpose: sets, prefixes, ranges.

Now you will write a function that deepens union-find. This summary unites the group's first concept in a single piece of code.

Exercise count_sets function

Write count_sets(n). init_parent is given; do union(0,1) and union(2,3), return the number of distinct roots. Print 2 with print(count_sets(4)).

Show example solution

def init_parent(n):
    # Return parent array
    return list(range(n))
def count_sets(n):
    # Count distinct sets after unions
    parent = init_parent(n)
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    def union(x, y):
        parent[find(x)] = find(y)
    union(0, 1)
    union(2, 3)
    roots = set(find(i) for i in range(n))
    return len(roots)
print(count_sets(4))

Test yourself

What does union-find track?
- A single node
- Edge weights
- Ranges
- Sets
Show answer

Sets — Union-find tracks sets.

find loop

while parent[x] ____ x:

Show answer

while parent[x] != x:

Summary - Advanced structures: match the terms

union-find

Sets
trie

Prefixes
segment tree

Ranges
parent

Parent

Next lesson: Challenge 1

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies