Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Parity disjoint set: maintain same-or-different constraints

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A parity disjoint set stores an XOR bit from each member to its parent. The bit expresses whether the member has the same or opposite binary label as the parent; absolute labels are unnecessary. Find returns both the component leader and accumulated parity to that leader, compressing the path while updating the stored bit. Constrain merges two components under a required same-or-different relation, or checks a relation already implied within one component. Union by size keeps the parent forest shallow. A failed constraint returns false and leaves the existing accepted constraints intact; it does not repair a contradiction by rewriting old edges.

Operational case

Asset A-19 must differ from A-47, and A-47 must differ from A-61. Both constraints are accepted. Their XOR composition makes A-19 and A-61 the same, so a request that they differ is rejected. A-83 belongs to a separate component, so its relationship to A-19 is unknown. This handles online additions of binary constraints and is a compact bipartite-consistency check for an evolving undirected graph. It does not support removing accepted constraints: after a deletion, old parity paths could continue to imply a relationship no longer justified by live edges.

Working Python program

python
"""Disjoint-set union with XOR parity for same/different asset constraints."""


class ParityGroups:
    def __init__(self, assets: list[str]):
        if len(assets) != len(set(assets)):
            raise ValueError("asset IDs must be unique")
        self.parent = {asset: asset for asset in assets}
        self.size = {asset: 1 for asset in assets}
        self.to_parent = {asset: 0 for asset in assets}

    def find(self, asset: str) -> tuple[str, int]:
        parent = self.parent[asset]
        if parent == asset:
            return asset, 0
        leader, parent_parity = self.find(parent)
        self.to_parent[asset] ^= parent_parity
        self.parent[asset] = leader
        return leader, self.to_parent[asset]

    def constrain(self, first: str, second: str, different: bool) -> bool:
        first_root, first_parity = self.find(first)
        second_root, second_parity = self.find(second)
        required = int(different)
        if first_root == second_root:
            return first_parity ^ second_parity == required
        if self.size[first_root] < self.size[second_root]:
            first_root, second_root = second_root, first_root
        self.parent[second_root] = first_root
        self.to_parent[second_root] = first_parity ^ second_parity ^ required
        self.size[first_root] += self.size[second_root]
        return True

    def relationship(self, first: str, second: str) -> str:
        first_root, first_parity = self.find(first)
        second_root, second_parity = self.find(second)
        if first_root != second_root:
            return "unknown"
        return "different" if first_parity ^ second_parity else "same"


groups = ParityGroups(["A-19", "A-47", "A-61", "A-83"])
print(groups.constrain("A-19", "A-47", True))
print(groups.constrain("A-47", "A-61", True))
print(groups.relationship("A-19", "A-61"))
print(groups.constrain("A-19", "A-61", True))
print(groups.relationship("A-19", "A-83"))

Output

Output
True
True
same
False
unknown

Time, space, and tradeoff

Each accepted union or find has amortized O(alpha(N)) time over a sequence of operations, where alpha is the inverse Ackermann function. The parent, size, and parity maps use O(N) space. The recursive find uses call-stack space bounded by the current parent path; union by size keeps that path logarithmic before compression. The chosen representation uses dictionary lookups for string IDs. For a fixed compact numeric ID space, arrays reduce overhead. To support deletions over known time windows, use rollback with an offline lifetime tree; ordinary path compression cannot be rolled back without recording additional changes.

Common Mistakes

  • Do not store only a leader if queries need same-or-different parity.
  • Do not compress a path without composing its parity to the new parent.
  • Do not merge two leaders before checking a same-component contradiction.
  • Do not claim ordinary disjoint sets can delete accepted constraints.

Connected lessons

Apply the invariant in the sparse readings and task constraints project, then check the operations quiz.

Potential disjoint sets: preserve numeric differences across merges adds a distinct structure contract to compare.

data structures
range-query-structures
Storage details