Connectivity under added links

An adjacency-list baseline runs BFS for each query, O(V + E) per query. Another baseline labels every vertex by component and rewrites all labels on a merge, costing O(V) per successful union. Both are reasonable for small workloads, but neither uses the addition-only contract to avoid repeated work.

Represent each component as a rooted tree. A root points to itself. find follows parents to the root and then rewrites traversed parents directly to that root (path compression). union finds both roots; equal roots mean no change. Otherwise attach the smaller root under the larger root and add their sizes.

following parent pointers ends at exactly one root, and two vertices are connected exactly when those roots match. Linking roots from different trees cannot create a cycle. Compression preserves the reached root, so it changes representation without changing connectivity. Sizes are authoritative at roots only; reading an old child's size as a component size is a bug.

Initialization is O(V) time/space. Union by size alone bounds depth by O(log V): a vertex's tree at least doubles whenever its depth increases. With compression, a sequence of M operations costs O((V + M) α(V)), where inverse Ackermann α grows extremely slowly. This is an amortized bound, not a claim that every operation has one step. The iterative implementation uses O(1) auxiliary space per operation.

Follow-up 1 — inspect compression. Predict 3's parent after find(3) and draw the changed forest. Connectivity remains identical while future lookups shorten.

Follow-up 2 — remove a link. A parent pointer is not an original network edge; deleting it cannot correctly split the graph. For infrequent removals, rebuild components from retained edges. For offline additions/removals, discuss interval processing with rollback DSU, usually avoiding compression so changes are undoable. An online fully dynamic graph is a different problem and needs a new contract.

Senior depth includes an independent BFS/component-label oracle and careful amortized bounds. Lead depth asks whether addition-only semantics actually fit the product before choosing this compact representation.

Reference: solution.py (download file, source below). Tests include seeded component-label comparison, repeat/self links, compression, and invalid vertices.

"""Explicit forest with union by size and iterative path compression."""


class DisjointSet:
    def __init__(self, n):
        if type(n) is not int or n < 0:
            raise ValueError("nonnegative integer size required")
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def _check(self, node):
        if type(node) is not int or not 0 <= node < len(self.parent):
            raise IndexError("unknown node")

    def find(self, node):
        self._check(node)
        root = node
        while root != self.parent[root]:
            root = self.parent[root]
        while node != root:
            next_node = self.parent[node]
            self.parent[node] = root
            node = next_node
        return root

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

    def connected(self, a, b):
        self._check(a)
        self._check(b)
        return self.find(a) == self.find(b)

python -m unittest discover -s curriculum/01-code/02-data-structures-algorithms/problems/23-disjoint-set-connectivity -p 'test_*.py'