DSA Disjoint Sets

How it works

Path halving shortens parent chains during find, while union by size attaches the smaller root beneath the larger one. The size values are meaningful at component roots, not arbitrary interior nodes. An attempted union inside one component returns False and does not reduce the component count. This local structure tracks connectivity only; it does not store the actual connecting routes or solve a directed reachability problem.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as disjoint-sets.py and run python disjoint-sets.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

class DisjointSet:
    def __init__(self, vertices):
        vertices = list(vertices)
        if len(set(vertices)) != len(vertices):
            raise ValueError("Repeated vertex")
        self.parent = {vertex: vertex for vertex in vertices}
        self.size = {vertex: 1 for vertex in vertices}
        self.components = len(vertices)

    def find(self, vertex):
        if vertex not in self.parent:
            raise ValueError("Unknown vertex")
        while self.parent[vertex] != vertex:
            self.parent[vertex] = self.parent[self.parent[vertex]]
            vertex = self.parent[vertex]
        return vertex

    def union(self, first, second):
        first, second = self.find(first), self.find(second)
        if first == second:
            return False
        if self.size[first] < self.size[second]:
            first, second = second, first
        self.parent[second] = first
        self.size[first] += self.size[second]
        self.components -= 1
        return True

groups = DisjointSet(["gate", "oak", "pond"])
print(groups.union("gate", "oak"))
print(groups.union("oak", "gate"))
print(groups.components)
print(groups.find("gate") == groups.find("oak"))

Expected result

True
False
2
True

The second union is redundant and the isolated pond keeps the total at two components. The property tests compare connectivity with an independent small graph model rather than assuming a particular root name must always be chosen.

Time, space and assumptions

With union by size and path compression/halving, a sequence of operations has near-constant amortized inverse-Ackermann cost under ordinary dictionary assumptions. Storage is O(V); a single operation is not promised worst-case O(1).