Python union-find: connected groups with path compression

Operation contract

The receipt-group fixture assigns bounded integer indexes. find follows parent links and shortens them toward the root; union attaches the smaller tree under the larger one. Repeatedly joining an already-connected pair returns False and leaves the group count unchanged. Representative indexes are implementation details, so callers ask whether two members share a root rather than requiring a specific root number.

Failure and ownership boundary

This structure handles additions to connectivity. Removing an edge cannot simply undo a union because previous paths and size records have already changed. The class accepts only indexes within its declared capacity and rejects bool. Python graph BFS: mark a vertex when it enters the queue can rebuild connectivity when deletions change the graph.

Working program

class ReceiptGroups:
    def __init__(self, count):
        if type(count) is not int or not 0 <= count <= 128:
            raise ValueError("group budget")
        self.parent = list(range(count))
        self.size = [1] * count
        self.groups = count
    def find(self, member):
        if type(member) is not int or not 0 <= member < len(self.parent):
            raise ValueError("member index")
        while member != self.parent[member]:
            self.parent[member] = self.parent[self.parent[member]]
            member = self.parent[member]
        return member
    def union(self, first, second):
        left, right = self.find(first), self.find(second)
        if left == right:
            return False
        if self.size[left] < self.size[right]:
            left, right = right, left
        self.parent[right] = left
        self.size[left] += self.size[right]
        self.groups -= 1
        return True

groups = ReceiptGroups(4)
print(groups.union(0, 1), groups.union(1, 2), groups.union(0, 2))
print(groups.find(0) == groups.find(2), groups.groups)

Output

True True False
True 2

Costs and limits

Initialization takes O(n) space and time. Union by size with path compression gives very small amortized parent work over a sequence of operations; an individual first find can still follow a logarithmic-depth tree before compression.

Common Mistakes

• Do not expose representative identity as a permanent business ID.
• Deleting an edge is not supported by reversing one parent assignment.

Connected lessons

Python graph BFS: mark a vertex when it enters the queue, Python dictionaries: insertion order and duplicate-key replacement, Python iterative tree traversal: shared nodes are not a tree.

Related Python operation checks

Python Kruskal: minimum spanning forests and disconnected graphs.