Union-Find

Union-Find Union-Find, aka Disjoint Set, is a rooted tree data structure that can efficiently classifies elements into categories. By utilizing this data structure, it becomes possible to rapidly determine whether two elements belong to the same group, as well as to swiftly merge two groups. Implementation in Python class UnionFind: def __init__(self, n): # Initialize all parents as -1, which means all nodes are root nodes self.parent = [-1] * n # Rank holds a weight to determine which tree has more weight # The tree with a smaller rank should be placed under the tree with a greater rank to keep the height of the merged tree smaller self.