Detect a Cycle in an Undirected Graph

Given an undirected graph with V vertices (0 .. V-1) and an edge list edges (no self-loops or duplicate edges), return true if it contains a cycle and false otherwise.

Hints

· Stuck? Reveal one nudge at a time.

In an undirected graph, an edge to an already-visited vertex (other than your parent) closes a cycle.

Track the parent so the edge you arrived on isn't mistaken for a cycle.

Union-Find alternative: an edge whose endpoints are already in the same set forms a cycle.

Common doubts

Every vertex has an edge back to its parent; without excluding it, that edge would falsely look like a cycle.

If both endpoints of an edge are already connected, adding the edge creates a second path between them — a cycle.

Yes — same parent-tracking idea; just watch out for recursion depth on large graphs.

Interview follow-ups

· What an interviewer asks next.

The parent trick fails; use a recursion stack (back edge) or Kahn's algorithm.

Track parents and, on detecting a cycle, walk back from both endpoints to their meeting point.

Fun facts

A connected undirected graph is a tree iff it has exactly V-1 edges and no cycle.
Union-Find's cycle check is the core of Kruskal's MST algorithm.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: V = 3, edges = [[0,1],[1,2],[2,0]]
Output: true
The three edges form a triangle.

Example 2

Input: V = 4, edges = [[0,1],[1,2],[2,3]]
Output: false
A path has no cycle.

Constraints

- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - no self-loops or duplicate edges

In an undirected graph, a cycle shows up as an edge that reconnects two already-connected vertices. Two clean detectors:

Traversal with parent tracking. BFS/DFS each component; a cycle exists if you reach an already-visited vertex that isn't the parent you came from. The parent check is crucial — the edge back to your immediate parent is not a cycle, just the edge you arrived on.

Union-Find. Process edges; for each (u, v), if u and v are already in the same set, this edge forms a cycle. Otherwise union them. A single pass over the edges, near-O(E·α).

Prerequisites

Before you start

· Concepts used directly in the solution.

Parent tracking. skip the edge back to the vertex you came from.

Union-Find. same-set endpoints ⇒ a cycle-closing edge.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Could the graph be disconnected?”

Yes — check every component.

“Self-loops or parallel edges?”

Assumed absent here; both would count as cycles if present.

The ideal opening — say it like this

I BFS each component tracking the parent; reaching a visited non-parent vertex means a cycle.

Or union-find: an edge whose endpoints already share a set closes a cycle.

Understand the problem

Worked example — V = 3, edges [[0,1],[1,2],[2,0]]

union 0-1, union 1-2, then edge 2-0: 2 and 0 already connected -> cycle

Key observations

1Aha

Extra edge = cycle

Beyond a spanning tree's V-1 edges per component, any edge closes a cycle.

2Aha

Parent check is essential

Reaching the parent isn't a cycle; reaching any other visited vertex is.

3Aha

Check every component

A cycle can hide in any disconnected piece.

Brute force vs optimal

	BFS + parent	Union-Find
Signal	visited non-parent neighbour	edge within one set
Time	O(V+E)	O(E·α)
Best when	graph given up front	edges stream in

Both detect the same cycles. Full code is in the Approaches selector below.

Summary

Key takeaway

A cycle is a redundant edge. Traverse tracking parents (visited non-parent ⇒ cycle), or union edges (same-set endpoints ⇒ cycle). Near-linear.

bfs: if neighbour visited and != parent -> cycle
dsu: if find(u) == find(v) -> cycle else union