Back to ChallengesDetect Cycle in an Undirected GraphMedium 25 min

Detect Cycle in an Undirected Graph

Given an undirected graph with **n** vertices and a list of edges, determine whether the graph contains a **cycle**.

Input: n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]

Output: true

0-1-2-3-0 forms a cycle.

Input: n = 4, edges = [[0,1],[1,2],[2,3]]

Output: false

A simple path, no cycle.

Time

O(V + E) with DFS, or O(E) with Union-Find.

Space

O(V) for visited array / parent map.

#1 — Simple cycle

Input: n=4 edges=[[0,1],[1,2],[2,3],[3,0]]

Expected: true

#2 — Tree, no cycle

Input: n=4 edges=[[0,1],[1,2],[2,3]]

Expected: false

#3 — Two disconnected trees

Input: n=5 edges=[[0,1],[1,2],[3,4]]

Expected: false

Interactive graph explorer available!

Switch to the Visualize tab to build a custom graph and animate BFS traversal to test your intuition.

Output

Click "Run Code" to see output here...