Union-find or repeated graph traversal for connectivity queries as edges keep arriving?

## The selection axis is time, not topology Both candidates answer the same question — are these two nodes in the same connected component? — and both are correct. What separates them is *when the edges arrive relative to the queries*, and that is the axis a candidate is expected to name out loud. Picture a logistics network. Warehouses are nodes; a new transfer lane between two of them is an edge. Two very different products sit on this data: - **Offline / static.** The lane table is loaded at start of day and does not change. Planners then ask thousands of "can goods reach B from A?" questions against that fixed snapshot. - **Online / incremental.** Lanes are commissioned through the day, and each commissioning is followed by connectivity checks from the routing service. ## The offline case: one traversal, then labels With all edges known, run a single sweep over the graph — repeatedly pick an unvisited vertex and explore everything reachable from it, stamping each visited vertex with the same component label. That is one O(V+E) pass in total, whatever traversal order you use. Afterwards each query is `label[a] == label[b]`, genuinely O(1). This is worth defending against the reflex to reach for a fancy structure: it is less code, it needs no extra invariant, and as a by-product you have the component sizes and membership, which reports usually want anyway. Reaching for a specialised structure when a single pass would do is a real interview mistake in the opposite direction from the usual one. The failure mode in this quadrant is running a *fresh* traversal per query: O(V+E) each, so q queries cost O(q(V+E)). On a graph with a hundred thousand edges and a thousand queries that is a hundred million edge visits to answer a thousand yes/no questions. ## The online case: disjoint-set union When edges arrive between queries, the label array from the offline trick is invalidated by every new edge — merging two components would require relabelling one of them, which is another linear pass. Disjoint-set union is exactly the structure for this: each component is represented by one element, `find(x)` returns that representative, and `union(a, b)` merges two components by linking one representative under the other. A connectivity query is `find(a) == find(b)`. With both standard optimisations — union by rank or size, so the shallower tree is attached under the deeper one, and path compression, so every traversed node is re-pointed at the representative — a sequence of m operations over n elements costs O(m · α(n)), where α is the inverse Ackermann function. That is *amortized near-constant*, not strictly O(1): the bound is on the whole sequence, and α(n) is at most a very small number for any n you will ever store. Stating it as "O(1) per operation" is the sloppy version and interviewers notice. The cost model comparison, for m edge additions and q queries: | Approach | Add an edge | One query | Total | | --- | --- | --- | --- | | Traversal per query | O(1) | O(V+E) | O(q(V+E)) | | One traversal, then labels | invalidates labels | O(1) | O(V+E) once, but static only | | Disjoint-set union | amortized ~O(1) | amortized ~O(1) | O((m+q)·α(n)) | ## What pushes you back to traversal Three requirements disqualify plain disjoint-set union even when the workload is online: 1. **You need the path, not the verdict.** Union-find knows that two nodes are in one component; it cannot tell you the route, because the representative tree is not the graph — path compression has deliberately rewired it for lookup speed. If the answer must be "yes, via these three lanes", you need a traversal, and if the lanes are weighted you need a shortest-path algorithm rather than either candidate. 2. **Edges are removed as well as added.** The structure only merges; there is no cheap split. A workload where lanes are decommissioned needs either a rebuild from the surviving edges, an offline technique that processes the whole operation sequence in a different order, or a genuinely more complex dynamic-connectivity structure. Recognising that deletion is the breaking requirement is the strongest signal a candidate can give here. 3. **The question is about something other than connectivity.** Distance, bipartiteness by traversal, cycle detection in a directed graph, ordering — union-find answers none of these directly; it answers "same component" and closely related grouping questions. ## How to narrate the choice A good answer takes about three sentences: name the interleaving ("edges and queries alternate, so the edge set is never final"), give the cost of the naive option ("a traversal per query is O(V+E) each"), and pick with the qualifier attached ("disjoint-set union, amortized near-constant per operation — assuming edges are only ever added"). That last clause is what distinguishes someone who has used the structure from someone who has memorised its name.