{ }SolveLogs
⌕
Home / Graphs / GFG
GeeksforGeeks Medium

Detect Cycle in Undirected Graph (DFS)

Detect Cycle in an Undirected Graph is a GFG problem (Medium). You get V vertices numbered 0 … V-1 and a list edges, where each [u, v] joins u and v in both directions. Return true if the graph contains a cycle and false otherwise.

  • A cycle is a closed walk that returns to its starting vertex without reusing an edge. Going out along an edge and straight back along the same edge does not count.
  • The graph can be disconnected; a cycle in any one component makes the answer true.
  • A self-loop, an edge from a vertex to itself, is a cycle on its own.
  • This page solves it with depth-first search.
Constraints
  • 1 <= V <= 10⁵
  • 0 <= E <= 10⁵
  • 0 <= edges[i][0], edges[i][1] < V
graphdfscycle
Open on GeeksforGeeks ↗
02

Intuition

DFS lays down a tree as it goes: stepping from u into an unvisited v makes u the parent of v. A tree has exactly one route between any two vertices, so a cycle is precisely a second route.

When DFS at u meets a neighbour that is already visited, there are only two cases:

  • it is u's parent: that is the edge DFS just walked down, seen from the other end, because an undirected edge is stored at both ends;
  • it is anything else: a back edge, a second connection, and therefore a cycle.

That is the whole trick to detect cycle in undirected graph using DFS: carry the parent into each call and excuse exactly that one neighbour.

How to spot this pattern

Any question that boils down to "is this undirected graph a forest?" is cycle detection in undirected graph form: Graph Valid Tree (LeetCode 261) is a cycle check plus a connectivity check, and Redundant Connection (LeetCode 684) asks which edge closes the first cycle. Reach for DFS cycle detection with a parent when you already have an adjacency list; reach for Union-Find when edges arrive one at a time.

03

Approach

Try it first

Before reading on: run DFS with only a visited array on the two-vertex graph with the single edge 0–1. What does vertex 1 see when it scans its neighbours? What single extra value per call would stop that from counting as a cycle?

1

Store every edge at both ends

For each [u, v], append v to adj[u] and u to adj[v]. The edge has no direction, so each end must see the other; this double storage is also why the parent later shows up as a visited neighbour.

2

Mark the vertex and remember its parent

dfs(u, parent) sets visited[u] = True before scanning anything, so a route that loops back to u finds it already marked. The root gets parent = -1, a value no vertex has, so it excuses nobody.

3

Classify each neighbour

For each v in adj[u]:

  • unvisited: a tree edge, so recurse with dfs(v, u) and return true at once if that call found a cycle;
  • visited and equal to parent: the edge you arrived on, so skip it;
  • visited and not parent: a back edge, so return true.
4

Return false when the list runs out

If every neighbour was new or the parent, nothing below u closes a loop. Returning false lets the caller carry on with its own next neighbour.

5

Start from every unvisited vertex

Loop s over all vertices and call dfs(s, -1) for each one still unvisited. One call only covers one component, and a cycle in any component makes the answer true.

04

Detect Cycle in Undirected Graph (DFS) solution in Python | C++ | Java

▶1class Solution:
▶2 def isCycle(self, V: int, edges: List[List[int]]) -> bool:
▶3 adj = [[] for _ in range(V)]
▶4 for u, v in edges:
▶5 adj[u].append(v)
▶6 adj[v].append(u)
▶7 visited = [False] * V
▶8 
▶9 def dfs(u, parent):
▶10 visited[u] = True
▶11 for v in adj[u]:
▶12 if not visited[v]:
▶13 if dfs(v, u):
▶14 return True
▶15 elif v != parent:
▶16 return True
▶17 return False
▶18 
▶19 for s in range(V):
▶20 if not visited[s] and dfs(s, -1):
▶21 return True
▶22 return False
dfs treeadjacencyempty011024213324413visited all falsetree edgeparent, skippedback edge
visited[F, F, F, F, F]V = 5
Every edge is stored twice, once in each endpoint's list, so the vertex you just came from always shows up again as a visited neighbour. The fix is to pass the parent into each call and excuse exactly that one neighbour. Any other visited neighbour is a second route back into the tree, which is a cycle.
dfs treeadjacency0011024213324413start dfs(0, -1)tree edgeparent, skippedback edge
u0dfs(0, parent = -1)
componentsfirst
Start at 0 with parent -1, a value no real vertex has, so the root never excuses any neighbour. Marking 0 visited now means any later edge back into it is noticed.
dfs treeadjacency010110242133244131 unvisited → dfs(1, 0)tree edgeparent, skippedback edge
u1dfs(1, parent = 0)
checked0 – 11 was unvisited
From 0, neighbour 1 is unvisited, so the edge 0–1 becomes a tree edge and DFS goes down into 1, handing it 0 as its parent. 1 is marked visited on entry, before any of its own neighbours are looked at.
dfs treeadjacency010110242133244130 is the parent → skiptree edgeparent, skippedback edge
checked1 – 00 is visited
parent0same edge, skip it
0 is visited, but it is 1's parent: this chip is the other copy of the edge DFS just came down. Walking it back is not a new route, so it proves nothing. Without the parent check, every graph with a single edge would report a cycle here.
dfs treeadjacency0120110242133244132 unvisited → dfs(2, 1)tree edgeparent, skippedback edge
u2dfs(2, parent = 1)
checked1 – 22 was unvisited
From 1, neighbour 2 is unvisited, so the edge 1–2 becomes a tree edge and DFS goes down into 2, handing it 1 as its parent. 2 is marked visited on entry, before any of its own neighbours are looked at.
dfs treeadjacency0120110242133244131 is the parent → skiptree edgeparent, skippedback edge
checked2 – 11 is visited
parent1same edge, skip it
1 is visited, but it is 2's parent: this chip is the other copy of the edge DFS just came down. Walking it back is not a new route, so it proves nothing. Without the parent check, every graph with a single edge would report a cycle here.
dfs treeadjacency01230110242133244133 unvisited → dfs(3, 2)tree edgeparent, skippedback edge
u3dfs(3, parent = 2)
checked2 – 33 was unvisited
From 2, neighbour 3 is unvisited, so the edge 2–3 becomes a tree edge and DFS goes down into 3, handing it 2 as its parent. 3 is marked visited on entry, before any of its own neighbours are looked at.
dfs treeadjacency01230110242133244132 is the parent → skiptree edgeparent, skippedback edge
checked3 – 22 is visited
parent2same edge, skip it
2 is visited, but it is 3's parent: this chip is the other copy of the edge DFS just came down. Walking it back is not a new route, so it proves nothing. Without the parent check, every graph with a single edge would report a cycle here.
dfs treeadjacency012340110242133244134 unvisited → dfs(4, 3)tree edgeparent, skippedback edge
u4dfs(4, parent = 3)
checked3 – 44 was unvisited
From 3, neighbour 4 is unvisited, so the edge 3–4 becomes a tree edge and DFS goes down into 4, handing it 3 as its parent. 4 is marked visited on entry, before any of its own neighbours are looked at.
dfs treeadjacency01234011024213324413back edge 4–1 → cycletree edgeparent, skippedback edge
checked4 – 11 visited, not the parent
cycle4 verticestree path + this edge
Back edge. 1 is already visited and it is not 4's parent (3). The tree already joins 1 down to 4; this edge is a second, independent way between them. Two routes between the same pair of vertices form a loop, so return true without checking anything else.
dfs treeadjacency01234011024213324413cycle found → return truetree edgeparent, skippedback edge
resulttruecycle through 1, 2, 3, 4
Cyclic. The red vertices are the loop: the tree path from 1 down to 4, closed by the back edge. The chips left uncoloured were never checked, because one back edge is enough.
05

Common pitfalls

Counting every visited neighbour as a cycle

✗ Wrong
for v in adj[u]:
    if visited[v]:
        return True
✓ Right
for v in adj[u]:
    if not visited[v]:
        ...
    elif v != parent:
        return True

The neighbour DFS came from is always visited, because the edge is stored at both ends. Without the parent test, a graph that is just 0–1 returns true.

Calling dfs but ignoring what it returns

✗ Wrong
if not visited[v]:
    dfs(v, u)
✓ Right
if not visited[v]:
    if dfs(v, u):
        return True

The back edge is usually found several calls deep. If the caller throws that True away, the loop carries on, the top-level call returns False, and a cyclic graph is reported as a forest.

Searching only from vertex 0

✗ Wrong
return dfs(0, -1)
✓ Right
for s in range(V):
    if not visited[s] and dfs(s, -1):
        return True
return False

In the third example the triangle 3–4–5 is not reachable from 0. A single search sees only the path 0–1–2 and answers false.

06

Edge cases

A long chain in Python

A path through 10⁵ vertices nests 10⁵ calls and hits Python's recursion limit. Either raise it with sys.setrecursionlimit, or push (vertex, parent) pairs on an explicit stack instead of recursing; the classification of each neighbour is unchanged.

07

Complexity

Time
O(V + E)
Space
O(V + E)
Detect cycle in undirected graph DFS is linear: each vertex is entered once, and each edge is looked at twice, once from each end, so the scan is O(V + 2E) = O(V + E). The adjacency list is O(V + E); the visited array and the recursion stack are O(V).
08

Detect Cycle in Undirected Graph (DFS) FAQ

How do you detect a cycle in an undirected graph using DFS?
  • Build an adjacency list with each edge stored at both ends.
  • dfs(u, parent): mark u visited, then for each neighbour v: recurse if unvisited, skip if v == parent, otherwise return true.
  • Call dfs(s, -1) from every unvisited vertex.
  • O(V + E) time, O(V + E) space.
Why pass the parent in DFS cycle detection?

Because an undirected edge appears in both endpoints' lists. When DFS reaches v from u, v's list contains u, which is already visited. That entry is the edge DFS just used, not a second route, so it must be skipped. The parent is the one visited neighbour that proves nothing.

What is a back edge in an undirected graph?

An edge from the current vertex to an already-visited vertex other than its parent. In an undirected DFS every non-tree edge is a back edge to an ancestor, so the graph has a cycle exactly when DFS finds one.

Can this method detect a cycle in a directed graph?

No. In a directed graph, reaching a visited vertex can be harmless: two separate paths may lead into the same vertex without forming a loop. Directed cycle detection needs a third state that marks vertices still on the current DFS path.

← Prev · GFG
Detect Cycle in Undirected Graph (BFS)
Next · GFG →
DFS of Graph