In an undirected graph, what does a union-find union that reports already connected tell you?
answer
- what happens when both ends already agree
- an edge that adds no new reachability
- accepted edges never close a loop
- the accepted set stays a forest
- count the merges that were refused
basics
~20 sThat the edge's two endpoints already sat in one component, so the edge closes a cycle — a second path between them already exists. Union-find therefore detects cycles in an undirected graph in a single streaming pass over the edges.
solid answer
~50 sEach edge is processed as one union: look up both endpoints' roots, and if they differ, merge — the edge joins two previously separate components. If the roots already match, the merge is refused, and that refusal is the cycle report: the two endpoints were already reachable from each other, so this edge creates a second route between them. Picture a facilities team stringing cables between office switches: every cable that reports already connected is redundant, adding a loop rather than reach. The successful unions build a spanning forest, so after processing every edge the component count is the element count minus the number of successful unions. Two caveats: this reasoning is for undirected edges only — a directed cycle needs a traversal-based method — and the structure tells you only that a cycle exists, never which vertices form it.
go deeper
Recall the rule crisply: compare the two endpoints' roots, merge when they differ, and treat a matching pair as the report that this edge closes a cycle.
Explain the forest invariant — accepted edges never close a loop, so the accepted set is always a spanning forest — and derive the remaining component count from vertices minus successful merges.
Demonstrate the limits under questioning: no directed edges, no cycle reconstruction, no edge removal, plus the self-loop and duplicate-edge cases that corrupt results on real, noisy input.
Own the modelling call: this technique fits a connectivity stream that only ever grows, so if the domain allows links to be retracted, say so early and choose the architecture around that rather than discovering it after the structure ships.
## The setup A facilities team is wiring an office floor. There are 8 switches and a growing pile of cables, each cable joining two switches. The team wants two things as each cable is added: is this cable actually extending the network, or is it a redundant loop? And how many separate islands of switches are still unconnected? Model the floor as an undirected graph: switches are vertices, cables are edges. Put the 8 switches into a union-find with 8 singleton sets, and process the cables one at a time. ## The rule For each edge (u, v): - Compute `find(u)` and `find(v)`. - If the roots **differ**, the endpoints are in different components. Merge them. This cable did real work: it joined two islands into one, and the component count drops by one. - If the roots **match**, the endpoints were already connected by some earlier chain of cables. Refuse the merge. This cable closes a **cycle** — there is now more than one route between u and v. That refusal is the entire cycle test. It falls out of the structure for free: you were going to call union anyway, and its boolean answer is the detector. ## Why the refusal really means a cycle The endpoints being in the same union-find set means there is already a path between them using edges accepted so far. Adding a further edge directly between the two ends of an existing path creates a closed walk — a cycle. Conversely, if the roots differ, no path yet exists between them, so the new edge cannot possibly close one; it strictly increases connectivity. This also proves an invariant worth stating in an interview: **the accepted edges always form a forest**. Every accepted edge merges two distinct trees, so no accepted edge ever closes a cycle, and by the end you hold a spanning forest of the graph — one spanning tree per connected component. ## Counting components Start the counter at the number of vertices and decrement on every successful merge. With 8 switches and 6 successful unions out of 10 cables, 2 components remain and 4 cables were redundant. This is a common interview add-on because it costs one integer. ## What the technique cannot do Be precise about the limits, because interviewers probe here: - **It does not recover the cycle.** You learn a cycle exists and which edge closed it; the vertex list requires a separate traversal between the two endpoints over the accepted edges. - **It does not apply to directed graphs.** Union-find merges symmetrically and has no notion of edge direction, so it happily reports a cycle for two edges pointing away from a common source — which is not a directed cycle at all. Directed cycle detection needs a traversal-based method that respects direction. - **It does not support removing an edge.** The structure only merges; there is no cheap way to undo a merge when a cable is unplugged. - **It is order-independent for the final answer but not per edge.** Whether a *particular* edge is the one flagged redundant depends on processing order; whether the graph contains a cycle at all does not. ## Two edge cases worth naming **Self-loop.** A cable from a switch back into itself gives `find(u) == find(u)` trivially, so it is reported as a cycle. That is correct — a self-loop genuinely is a cycle of length one. **Repeated edge.** Feeding the same pair twice reports the second copy as a cycle. In a multigraph that is right: two parallel edges form a cycle of length two. If your input is meant to be a simple graph and duplicates are just noisy data, deduplicate before processing or you will report cycles that the intended graph does not have. This is the practical bug in real cable inventories and real evidence streams, where the same fact arrives twice. ## Cost One pass over the edges, two lookups and at most one merge per edge, so O(E) operations on the structure, each near-constant amortized. Memory is O(V). Crucially the edges can arrive as a **stream** — you never need the whole graph resident, and you can answer connectivity queries interleaved with edge arrivals, which is what makes union-find the natural fit for a network that grows over time rather than a graph handed to you complete.
- How do you report how many components remain after processing every edge?Initialize a counter to the vertex count and decrement it once per successful merge; refused merges leave it alone. With 8 vertices and 6 successful merges, 2 components remain. The counter costs one integer and is exact at every point in the stream, not just at the end.
- Does this hand you the vertices that form the cycle?No — it reports existence plus the closing edge, nothing more. To recover the actual cycle you traverse the accepted edges between that edge's two endpoints and prepend the closing edge. The structure deliberately stores no adjacency information, which is exactly why it is so cheap.
- What do a self-loop and a duplicated edge do to this test?Both are reported as cycles. A self-loop truly is one, so that is correct. A duplicated pair is a cycle of length two in a multigraph but is usually just noisy input for a simple graph, so deduplicate edges first if repeated facts are expected — otherwise you will report loops the intended graph does not contain.
It is the facilities team asking, before plugging in each cable, whether these two switches can already reach each other; if they can, the cable adds a loop rather than reach.
saying these in an interview costs you the question
- Applies the same test to directed graphs unchanged
- Thinks the refused merge still joins the two sets
- Claims the structure returns the cycle's vertex list
- Believes the edges must be processed in some special order
- Counts every processed edge as one fewer component