Eight Nodes One Root
A DSU over elements 0..7 uses union by size, exactly as written in cp-algorithms:
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (size[a] < size[b])
swap(a, b);
parent[b] = a;
size[a] += size[b];
}
}
Note the tie rule this code produces: when the two roots have equal size, the root of the first argument stays on top. No find is ever called on its own, and there is no path compression.
These calls run in order:
| # | call |
|---|---|
| 1 | union_sets(0, 1) |
| 2 | union_sets(1, 2) |
| 3 | union_sets(3, 4) |
| 4 | union_sets(5, 6) |
| 5 | union_sets(6, 7) |
| 6 | union_sets(4, 5) |
| 7 | union_sets(2, 3) |
What is parent[0..7] at the end?
Sign in to answer questions and track your progress
Sign In