183. Detect a Cycle in an Undirected Graph

Given an undirected graph with n vertices and m edges, print 'Yes' if it contains a cycle, otherwise 'No'.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains two integers, an undirected edge. Output: Print 'Yes' if the graph contains a cycle, otherwise print 'No'.

1 <= n <= 10^5

This is meaningfully different from cycle detection in a DIRECTED graph (which needs to track the current recursion stack, not just parent) - undirected and directed cycle detection use genuinely different techniques, easy to conflate.

Check whether an undirected graph contains a cycle. Brute force: Try to find some sequence of edges forming a closed loop by exhaustively checking all possible paths - this is far more work than a single DFS/BFS pass tracking parents. Optimised: Tracking each vertex's PARENT during a single DFS/BFS pass lets you distinguish a genuine cycle (reaching an already-visited vertex that ISN'T your immediate parent) from simply walking back along the SAME edge you just came from (which is normal and expected in undirected graph traversal, not a cycle).

Process the edges one at a time with a disjoint-set-union structure (union by rank/size plus path compression): for each edge (u, v), check whether u and v are already in the same set - if so, this edge connects two already-connected vertices, meaning a cycle exists - otherwise union their sets. This is iterative rather than recursive, so it avoids the stack-depth risk that DFS has on a skewed graph, and each union/find operation runs in near-constant amortised time thanks to the inverse Ackermann bound, making it both simple and robust at the given scale. Time: O(m * α(n)) Space: O(n)

Run a DFS from each unvisited vertex, passing along the parent it was reached from; if the DFS ever encounters a neighbour that has already been visited and is not the immediate parent, a back edge has been found, meaning a cycle exists. This performs a single traversal of the whole graph rather than one per edge, giving a direct linear-time answer, though on a graph with up to 10^5 vertices arranged as a long path, recursive DFS risks a deep call stack. Time: O(n+m) Space: O(n)

For every edge (u, v) in the graph, temporarily remove it and run a BFS or DFS to check whether u and v are still connected through some other route; if they are, that edge was part of a cycle, so the graph contains one. Checking all m edges this way is correct - a cycle exists exactly when some edge is 'redundant' for connectivity - but it repeats a full graph traversal once per edge, which is very wasteful. Time: O(m*(n+m)) Space: O(n+m)

1. Do a DFS (or BFS) from every unvisited vertex, tracking each vertex's PARENT in the traversal. 2. If you reach an ALREADY-VISITED vertex that ISN'T the current vertex's immediate parent, you've found a cycle. 3. If no such situation ever arises across the whole graph, there's no cycle.

Time: O(n + m) - one DFS/BFS pass (across all components) visiting every vertex and edge once. Space: O(n), for the visited array, parent tracking, and traversal stack/queue.

Test m = 0 (no edges, expect 'No'), a disconnected graph where only one component contains a cycle, and n at the upper bound of 10^5.

Be ready to explain WHY tracking parent is essential here specifically for UNDIRECTED graphs - without it, walking back along the same edge you just traversed would be incorrectly flagged as a cycle every single time.