Union Find | Disjoint Set Union Introductory Problem
Prerequisite: DSU/Union Find Fundamentals and DSU Optimizations
This practice turns the DSU template into a small class. The class receives a stream of operations over integer labels. A label can appear for the first time in any operation, so unlike the array version from the intro article, we cannot assume the elements are 0..n-1 ahead of time.
Complete the class so merge(x, y) merges the sets containing x and y, and is_same(x, y) returns whether x and y currently belong to the same set. The input uses the command name union, but the method you implement is called merge; they mean the same DSU operation.
Example
union 1 2 union 2 3 is_same 1 3 => true is_same 2 4 => false
After union 1 2, elements 1 and 2 share one root. After union 2 3, the element 3 joins that same set, so 1, 2, and 3 are connected. The query is_same(1, 3) returns true. The element 4 has not been merged with anything, so is_same(2, 4) returns false.