Cycle Detection in Undirected Graph

Implement cycle detection in an undirected graph using DFS with parent tracking.

graph dfs cycle-detection undirected

Given an undirected graph with n vertices labeled from 0 to n-1 and a list of edges (each edge is a pair [u, v]), determine if the graph contains a cycle. A cycle exists if there is a path of length >= 3 that starts and ends at the same vertex without reusing an edge immediately (and without repeating vertices except the start/end). Use the following signature:

def has_cycle(n: int, edges: list[list[int]]) -> bool:

Implement a depth-first search (or union-find) approach to detect cycles. The graph may be disconnected. Return True if the graph contains at least one cycle, otherwise False.

Constraints

1 <= n <= 10^5
0 <= len(edges) <= 10^5
Each edge is [u, v] with 0 <= u, v < n and u != v.
The graph is undirected, meaning each edge connects both u->v and v->u.
Expected time complexity: O(n + len(edges)).

Example

>>> has_cycle(4, [[0,1],[1,2],[2,0]])
True
>>> has_cycle(4, [[0,1],[1,2],[2,3],[3,0]])
True
>>> has_cycle(3, [[0,1],[1,2]])
False
>>> has_cycle(5, [[0,1],[1,2],[2,3],[3,4]])
False

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use DFS with a visited array and a parent tracking to avoid going back to the immediate previous node.

If you encounter an already visited neighbor that is not the parent, a cycle exists.

Also consider the union-find approach: if two vertices of an edge are already in the same set, a cycle exists.

The graph may be disconnected, so run DFS from each unvisited vertex.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.