Union-find

A structure that answers are these two joined, and merges groups, both in nearly constant time.

Key idea

Each group is a tree with a representative

Every element points at a parent. Following parents leads to a root, and that root is the group's representative. Two elements are in the same group exactly when they have the same root.

Merging two groups is one assignment: point one root at the other. That is why it is fast.

1def make(n):2    return list(range(n))          # each element is its own root3 4def find(parent, x):5    while parent[x] != x:6        parent[x] = parent[parent[x]]     # path halving7        x = parent[x]8    return x9 10def union(parent, a, b):11    root_a, root_b = find(parent, a), find(parent, b)12    if root_a == root_b:13        return False               # already joined, this edge is redundant14    parent[root_b] = root_a15    return True16 17parent = make(5)18print(union(parent, 0, 1), union(parent, 1, 2), union(parent, 0, 2))19print(find(parent, 2) == find(parent, 0), find(parent, 3) == find(parent, 0))

Code lab· 30 min

Union-find drills

Build the structure, then read it twice. find returns a root, compressing as it goes. union joins two groups and reports whether they were separate. largest_group returns the size of the biggest group once every edge has been applied. edges_until_connected returns how many edges had to be processed before everything became one group, or -1 if that never happens.

solution.py

Tests

print(largest_group(5, [(0, 1), (1, 2), (3, 4)]), largest_group(3, []), largest_group(0, []))print(edges_until_connected(4, [(0, 1), (2, 3), (1, 2)]), edges_until_connected(4, [(0, 1), (2, 3)]), edges_until_connected(1, []))parent = make(4)print(union(parent, 0, 1), union(parent, 1, 0))print(find(parent, 0) == find(parent, 1))

Output

Run tests to see output.

Problem· 20 min

Number Of Connected Components In An Undirected Graph

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 22 min

Graph Valid Tree

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 22 min

Redundant Connection

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def make(n):2 return list(range(n)) # each element is its own root3 4def find(parent, x):5 while parent[x] != x:6 parent[x] = parent[parent[x]] # path halving7 x = parent[x]8 return x9 10def union(parent, a, b):11 root_a, root_b = find(parent, a), find(parent, b)12 if root_a == root_b:13 return False # already joined, this edge is redundant14 parent[root_b] = root_a15 return True16 17parent = make(5)18print(union(parent, 0, 1), union(parent, 1, 2), union(parent, 0, 2))19print(find(parent, 2) == find(parent, 0), find(parent, 3) == find(parent, 0))

print(largest_group(5, [(0, 1), (1, 2), (3, 4)]), largest_group(3, []), largest_group(0, []))print(edges_until_connected(4, [(0, 1), (2, 3), (1, 2)]), edges_until_connected(4, [(0, 1), (2, 3)]), edges_until_connected(1, []))parent = make(4)print(union(parent, 0, 1), union(parent, 1, 0))print(find(parent, 0) == find(parent, 1))