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

Online connectivity: answer after each edge change

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

Online connectivity answers a question against the graph that exists now, without knowing future edge changes. An undirected adjacency set gives an exact baseline: adding or removing an edge updates both endpoints, and a breadth-first search answers whether two depots share a path. This is deliberately a single-writer structure. A disjoint-set union can absorb additions cheaply but cannot reverse an arbitrary bridge deletion; the search recomputes reachability instead of pretending the old component partition is still valid. Duplicate adds and absent removals are errors, making the update contract observable rather than silently hiding a caller mistake.

Operational case

D-19 is connected to D-26, while D-47 starts isolated. The first question is false. Adding D-26 to D-47 makes the second question true; deleting that same edge makes the third false. A single removed edge can split a component, or it can leave an alternate route intact. The search detects either case from the remaining adjacency sets. This immediate-answer contract differs from an event batch whose future additions, deletions, and questions are all known before processing begins.

Working Python program

python
"""Exact online connectivity with adjacency sets and a fresh search per question."""

from collections import deque


class DepotNetwork:
    def __init__(self, depot_ids):
        depot_ids = tuple(depot_ids)
        if len(set(depot_ids)) != len(depot_ids):
            raise ValueError("duplicate depot")
        self.neighbors = {depot_id: set() for depot_id in depot_ids}

    def _check(self, first, second):
        if first not in self.neighbors or second not in self.neighbors:
            raise KeyError("unknown depot")
        if first == second:
            raise ValueError("self-edge")

    def connect(self, first, second):
        self._check(first, second)
        if second in self.neighbors[first]:
            raise ValueError("edge already active")
        self.neighbors[first].add(second)
        self.neighbors[second].add(first)

    def disconnect(self, first, second):
        self._check(first, second)
        if second not in self.neighbors[first]:
            raise ValueError("edge is absent")
        self.neighbors[first].remove(second)
        self.neighbors[second].remove(first)

    def connected(self, source, destination):
        if source not in self.neighbors or destination not in self.neighbors:
            raise KeyError("unknown depot")
        visited = {source}
        pending = deque([source])
        while pending:
            depot = pending.popleft()
            if depot == destination:
                return True
            for adjacent in self.neighbors[depot]:
                if adjacent not in visited:
                    visited.add(adjacent)
                    pending.append(adjacent)
        return False


network = DepotNetwork(("D-19", "D-26", "D-47"))
network.connect("D-19", "D-26")
print(network.connected("D-19", "D-47"))
network.connect("D-26", "D-47")
print(network.connected("D-19", "D-47"))
network.disconnect("D-26", "D-47")
print(network.connected("D-19", "D-47"))

Output

Output
False
True
False

Time, space, and tradeoff

An add or remove performs expected O(1) hash-set work per endpoint and stores O(V + E) adjacency entries for V depots and E undirected edges. Each connectivity question takes O(V + E) time in the worst case and O(V) temporary space for the queue and visited set. The baseline is sensible when updates are common but questions are modest, or when correctness is more valuable than a complex update structure. High-query workloads can justify fully online connectivity machinery, but its replacement-edge search and amortized bounds require a separate, much larger implementation. This program does not supply thread safety or distributed agreement.

Common Mistakes

  • Do not leave the reverse adjacency entry behind when deleting an undirected edge.
  • Do not use a union-only component cache after deleting a possible bridge.
  • Do not treat a repeated add or missing-edge removal as a harmless no-op without specifying that policy.
  • Do not quote amortized bounds for an advanced online structure as the cost of this breadth-first search.

Connected lessons

Test this contract in the live depot audit project, then check the operations quiz.

Link-cut forests: change tree edges and sum a path adds a related operation contract.

Block-cut indexes: separate articulation depots from cyclic road blocks adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details