STEP 15 · GRAPHS · VISITED TWICE, AND NOT BY MY PARENT · MEDIUM

Detect Cycle in an Undirected Graph

WHAT IT SAYS

Determine whether an undirected graph contains any cycle.

WHAT IT'S REALLY ASKING

"A traversal exploring fresh territory never meets a visited node — unless two different routes lead to the same place, and two routes to one place IS a cycle. One nuance: in an undirected graph every edge points both ways, so the node you just came from always looks 'visited'. The signal is meeting a visited node that is NOT the one you arrived from."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Hunt for a path that returns to its start

O(V · (V + E)) — a full search per candidate start, with path bookkeeping

For each vertex, launch a DFS that tracks the current path, looking for any walk that leaves the vertex and comes back to it without reusing an edge. If any vertex admits such a round trip, report a cycle.

WHERE THE WORK IS WASTED — Cycles are being hunted per-starting-point, but a cycle through vertices a-b-c is discovered redundantly from a, from b, AND from c — the same structure certified three times by three searches. Deeper: the definition being chased ('a walk returning to start') is needlessly operational. A single traversal already generates enough evidence to convict: the moment ANY two distinct routes converge on one node, a cycle exists somewhere behind them, no round trip required. The per-start hunt rebuilds globally what one sweep observes locally.

KEY OBSERVATION — THE UNLOCKlink

Convergence convicts — except convergence with your own parent.

The clean claim: an undirected graph has a cycle if and only if, during a traversal, some node is reached that was ALREADY visited via a different route. Why: two distinct routes from the traversal's origin to one node form, together, a closed loop (walk out on route one, back on route two — distinctness guarantees some edge isn't retraced). Conversely, in an acyclic graph (a forest), there is exactly ONE simple path between any two nodes, so a traversal can never arrive anywhere twice by genuinely different routes. Now the nuance that separates this from the directed version, and it comes straight from representation: an undirected edge u-v is stored as two directed arcs, u→v and v→u. So the DFS standing at v (having arrived from u) sees u in its neighbour list — visited! — but this is not convergence of two routes; it is the SAME edge read backwards. The fix is one extra parameter: carry the parent (the node you arrived from), and exempt it from suspicion. The verdict becomes: a visited neighbour OTHER than my parent means a genuine second route — cycle. A visited neighbour that IS my parent is the echo of my own arrival — ignore. Be precise about what the parent-exemption assumes: simple graphs. Parallel edges (two distinct u-v edges) or self-loops ARE cycles, yet the naive exemption waves them through; if the input allows multi-edges, exempt the parent EDGE (by index), not the parent node. The graph may be disconnected, so sweep all vertices and launch from each unvisited one — the launches partition the graph, each searching one component, and any component may hold the cycle. The union-find alternative deserves its own sentence because its logic is pleasingly inverted: process edges one by one, uniting endpoints; an edge whose endpoints are ALREADY in the same set is announcing that a path between them existed before this edge — adding it closes a loop. Detection at insertion time, no traversal at all — the same 'second route' logic, restated as 'second connection'.

DFS with a parent parameter, launched per component

O(V + E) time for traversal or union-find (near-linear), O(V) space

For each unvisited vertex, DFS(v, parent = -1): mark v; for each neighbour u — if unvisited, recurse DFS(u, v) and propagate a found-cycle; else if u ≠ parent, return true. BFS variant: queue holds (node, parent) pairs, same exemption. Union-find variant: for each edge, if find(u) == find(v) return true, else union.

WHAT YOU TRADED — DFS answers 'is there a cycle?' in one pass but gives a static verdict; union-find detects at edge-insertion time — the right shape when edges stream in (Kruskal rejects cycle-closing edges with exactly this test) — at the cost of not yielding the cycle's vertices without extra work. The transferable lesson: cycles are convergence events — two routes meeting — and the entire difficulty of each graph variant is defining which convergences are REAL: here, everything but your parent; in directed graphs, only ancestors still on the stack (a stricter test, for a reason worth studying next).

WATCH THE IDEA RUN

the one exception visited, but it's my parent

verdict no cycle yet

In an undirected graph every edge is stored twice — u lists v, and v lists u. So a naive 'I reached someone already visited, therefore cycle!' fires immediately on every single edge, walking straight back where you came from.

step 1 / 10

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Second Route Means a Loop

YOU'LL SEE IT AGAIN WHEN

The question is existence of a cycle in an UNDIRECTED graph — so any revisit via a distinct route convicts, no path-stack needed.
Each edge is stored twice, so the arrival edge echoes as a visited neighbour — the parent exemption is mandatory, and it assumes no multi-edges.
Edges arrive incrementally or a spanning structure is being built — union-find's same-set test detects the loop at insertion.

SAME BLUEPRINT, DIFFERENT PROBLEM

Detect Cycle in a Directed Graph (why the parent trick fails there)Redundant Connection (union-find framing verbatim)Graph Valid Tree (acyclic + connected)Kruskal's Minimum Spanning Tree (cycle rejection as the core step)

The bar isn't "solved it once." It's "could rebuild it from the observation."