The Second Cycle Wins
A DSU stores, for every element, the parity of the path length from that element to its root, so find(v) returns the pair (root, parity). An edge (a, b) asserts that a and b get different colours. When both endpoints already share a root, the edge is rejected if their parities are equal.
Edges arrive in this order on vertices 1..4:
| step | edge |
|---|---|
| 1 | (1, 2) |
| 2 | (3, 4) |
| 3 | (2, 3) |
| 4 | (1, 4) |
| 5 | (2, 4) |
Which step is the first one the structure rejects?
Sign in to answer questions and track your progress
Sign In