Disjoint Sets

Union-Find (Disjoint Set Union)

Union-Find (Disjoint Set Union) Problem Definition Given N mutually disjoint sets, we need to support two operations: Merge: Union two sets together Query: Determine whether two elements belong to the same set Example Operation Sequence Elements: a, b, c, d, e, f Operations: Merge(a,b), Merge(b,e), Merge(c,f), Merge(b,f) Approach 1: Naive Label-Based Assign each element a set ID. To merge, update all elements of one set to the other’s ID. Operation a b c d e f Init 1 2 3 4 5 6 Merge(a,b) 1 1 3 4 5 6 Merge(b,e) 1 1 3 4 1 6 Merge(c,f) 1 1 3 4 1 3 Merge(b,f) 1 1 1 4 1 1 Complexity: Query: O(1) | Merge: O(n)