DSA sheet · Graphs · Cycle detection pattern (DFS)

Detect a Cycle in an Undirected Graph (DFS)

We get an undirected graph and must say whether it contains a cycle: a loop you can walk around and come back to where you started. The teacher solves it with DFS and one extra piece of information carried into every call: the parent, meaning the node we just came from. "I found a node I have already seen, and it is not the one I just came from" = cycle. This idea comes back in the BFS version (Problem 13), and it is the reason the directed version (Problem 12) needs a different trick. Cycle detection is also the heart of course scheduling and deadlock checks, so it is worth getting fully clear.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Cycle detection with DFS + parent (the teacher's solution)
• Part B · The same idea with an explicit stack (no recursion limit)
• Part C · Revision page

Part 0 · Before starting

Graph words used on this page

• Node (also called a vertex): a point. Edge: a line joining two nodes. V = number of nodes, numbered 0 … V−1. E = number of edges.
• Undirected edge (0)—(1): you can walk it both ways, 0 to 1 and 1 to 0. Directed edge (0)→(1): only from 0 to 1. This page is about undirected graphs. Directed ones are Problem 12.
• Weighted edge: an edge with a cost written on it. Here edges have no weights; we only care whether they exist.
• Neighbours (the teacher also says "children"): the nodes joined to a node by one edge.
• Cycle: a walk that starts at a node, uses different edges, and comes back to the same node. In a simple undirected graph it needs at least 3 nodes, like a triangle. Walking 0 → 1 and straight back over the same edge is not a cycle.

  has a cycle                 no cycle (a "tree")
  (0)———(1)                   (0)———(1)
    \   /                       \
     (2)———(3)                   (2)———(3)
  loop: 0 → 1 → 2 → 0          every route back would reuse an edge

The three ways a graph can be given

Building the adjacency list from an edge list

Because the graph is undirected, the edge [u, v] means "v is a neighbour of u" and "u is a neighbour of v". So we store it twice, once in each list. The teacher's reasoning: if 0 can be the parent of 1, then 1 can just as well be the parent of 0.

V = 4
edges = [[0, 1], [0, 2], [1, 2], [2, 3]]

graph = [[] for _ in range(V)]   # one empty list per node
for u, v in edges:
    graph[u].append(v)           # u can go to v
    graph[v].append(u)           # and v can go to u (undirected)

print(graph)   # [[1, 2], [0, 2], [0, 1, 3], [2]]

The visited array, and why it's not optional

visited[x] says whether we have already reached node x. Without it, DFS would go 0 → 1 → 0 → 1 → … forever, because in an undirected graph every edge leads back. The teacher stresses this: in graphs, marking visited is what stops you from going round and round.

Connected components

A connected component is one separate piece of the graph: inside a piece you can reach every node, but there is no edge between pieces. This question says the graph may have several pieces (we met this in Number of Provinces, Problem 4). The teacher's examples:

  V = 8, E = 8:  two pieces of 4 nodes each
  (0)—(1)   (4)—(5)
   |   |     |   |
  (3)—(2)   (7)—(6)

  V = 5, E = 4:  the 5th node sits alone, with no edge at all
  (0)—(1)   (4)
   |   |
  (3)—(2)

A DFS from node 0 only reaches its own piece. If the cycle lives in another piece, we must start a new DFS there too. So the answer is: "is there a cycle in any piece?"

DFS with recursion, in 4 lines (see Problem 5 for the full version)

• Visit a node: mark it visited.
• For each neighbour that is not visited yet, call DFS on it. The current call pauses on the call stack until that call finishes.
• When a call finishes, the paused call continues with its next neighbour.
• The call stack always holds the current path from the start node down to where we are.

BFS (a queue, level by level, Problem 3) solves the same question in Problem 13. The teacher's point: this problem is only "traverse, mark visited, notice a repeat", so DFS and BFS both work. Pick whichever feels easier.

Part A · Cycle detection with DFS + parent

GFG: "Undirected Graph Cycle"

1The question in simple words

You are given V (number of nodes) and edges, a list of pairs [u, v]. Each pair is an undirected edge. The adjacency list is not given; we build it. Return True if the graph has a cycle anywhere, otherwise False. The graph may be split into several components.

  (0)———(1)
    \   /
     (2)———(3)
  0 → 1 → 2 → 0 is a loop

  (0)———(1)———(2)———(3)

  a straight line: no loop

2What the constraints tell us

• V and E can each be up to 10⁵. The teacher's rule of thumb: roughly 10⁸ simple steps is where TLE (Time Limit Exceeded) starts, and 10⁹ is a sure TLE. An O(V²) idea would be 10⁵ × 10⁵ = 10¹⁰, far too slow. So we need something linear: O(V + E).
• The same size also rules out an adjacency matrix (V² cells). An adjacency list it is.
• "May have multiple components" → we need an outer loop that starts a DFS in every piece.
• Python-only point: a DFS can go 10⁵ calls deep (a long line graph). Python's default recursion limit is 1000, so we raise it with sys.setrecursionlimit. Part B shows a version with no recursion at all.

3Intuition: a walk where you notice a familiar place

Picture walking through a town and leaving a chalk mark on every corner you pass. You keep walking forward, never turning straight back. If you reach a corner that already has your chalk mark, you must have walked in a loop. That's a cycle.

There is one catch. In an undirected graph, every road can be walked both ways. So from any corner, the corner you just came from is always one step away, and it always has a chalk mark. Seeing that mark proves nothing; you are just looking over your shoulder.

So the rule becomes: a neighbour that is already visited AND is not my parent (the node I came from) means a cycle. To use this rule, every DFS call must know its parent. That's the only extra thing compared to plain DFS.

4Building the logic from her examples

Step 1: why the parent check is needed (counter-example)

Try the naive rule "a visited neighbour means a cycle" on the smallest graph there is: one edge.

  (0)———(1)

  graph[0] = [1]
  graph[1] = [0]   ← the same edge, stored backwards

  dfs(0): mark 0
    neighbour 1: not visited → dfs(1)
      dfs(1): mark 1
        neighbour 0: visited! → "cycle" ✗ WRONG

Node 1 sees node 0 as visited only because we came from 0. The same edge 0—1 is stored as 1→0 too, so it shows up again. A cycle needs a different way back. That's why the teacher says the visited parent is "allowed" to be seen: you are looking backwards, not finding a loop.

Step 2: when a visited neighbour really means a cycle

Her main example, V = 4, edges [[0,1],[0,2],[1,2],[2,3]]. Start a DFS at 0 and carry the parent along:

  (0)———(1)          dfs(0, parent −1): mark 0, go to 1
    \   /            dfs(1, parent 0):  mark 1. 0 is visited but it is my parent → fine. Go to 2
     (2)———(3)       dfs(2, parent 1):  mark 2. Look at neighbour 0:
                       0 is visited, and my parent is 1, NOT 0
                       → someone else reached 0 before me → cycle!

Node 2 came from 1, so seeing 1 is normal. But 0 is also marked, and 2 didn't come from 0. Somebody reached 0 by another route. Her picture: you start at A, go to B (new), go to C (new), and then the road from C leads to a place you have already seen. You have been walking in a circle.

        start
          |
          w   ← visited earlier
         /  \
     (tree edges)
        ...    \
         u ———— w      the extra edge u—w closes the loop
  path w ⇢ u (tree edges) + edge u—w = cycle

Step 3: the starting node has no parent

The first call has come from nowhere, so the teacher passes −1 as its parent. −1 is not a real node number, so the check "nb != parent" is always true for the start node: every visited neighbour of the start (other than itself) would be a real cycle.

Step 4: what to do with an unvisited neighbour

Go into it: call dfs(nb, node). The neighbour is the new node, and the current node becomes its parent. If that call finds a cycle somewhere below, it returns True, and we must pass that True straight up. The teacher's example: calls go 8 → 9 → 10, and inside the call for 10 we see 8 visited (not 10's parent) → True. That True must travel back through 9 and 8 to the top. So we write if dfs(...): return True, not just dfs(...).

Step 5: many components → loop over all nodes, but start only at unvisited ones

Her example: suppose nodes 1 … 7 form one piece with no cycle, and 8, 9, 10 form a triangle. A DFS from 1 marks 1 … 7 and finds nothing. Do we start again from 2? No: 2 is already visited, so it was checked as part of 1's piece. Starting from it again would only repeat work. The first unvisited node is 8, which is a new piece. DFS from 8 finds the triangle → True.

  piece 1: no cycle                  piece 2: cycle
  (1)—(2)—(3)                        (8)———(9)
       |                               \   /
      (4)—(5)   (6)—(7)                 (10)
  (also joined somewhere, all reached from 1)

  outer loop: i = 1 → not visited → dfs → False
              i = 2 … 7 → visited → skip
              i = 8 → not visited → dfs → True → answer True

5Approach steps

1. Build the adjacency list graph, adding every edge both ways.
2. Make visited = [False] * V.
3. For every node i from 0 to V−1: if it's not visited, run dfs(i, -1). If it returns True, return True.
4. Inside dfs(node, parent): mark node visited.
5. For each neighbour nb: if nb is not visited → if dfs(nb, node) is True, return True.
6. Else (nb is visited): if nb is not the parent → return True (cycle).
7. After all neighbours → return False.
8. After the outer loop → return False (no piece had a cycle).

6Code (Python)

import sys
sys.setrecursionlimit(10**6)       # DFS can go V calls deep

class Solution:
    def isCycle(self, V, edges):
        graph = [[] for _ in range(V)]
        for u, v in edges:             # undirected: store both ways
            graph[u].append(v)
            graph[v].append(u)

        visited = [False] * V
        for i in range(V):             # one DFS per component
            if not visited[i]:
                if self.dfs(i, -1, graph, visited):
                    return True
        return False

    def dfs(self, node, parent, graph, visited):
        visited[node] = True
        for nb in graph[node]:
            if not visited[nb]:
                if self.dfs(nb, node, graph, visited):   # node is nb's parent
                    return True
            elif nb != parent:         # seen before, and not where I came from
                return True
        return False

7Code line by line

8Dry run

Dry run 1: the teacher's graph (has a cycle)

V = 4, edges [[0,1],[0,2],[1,2],[2,3]] → graph: 0:[1,2] · 1:[0,2] · 2:[0,1,3] · 3:[2]. "V" in the visited column means visited.

  snapshot at step 5 ([x] = visited)
  [0]———[1]
     \   /
      [2]———(3)        2 looks at 0: marked, and 2 came from 1 → cycle

In her spoken walk-through, node 2 checks 1 first (its parent, skipped) and then 0. With this edge order the code checks 0 first, because graph[2] = [0, 1, 3]. The answer is the same either way. Node 3 is never even visited: we stop as soon as the cycle is found.

Dry run 2: two components, the cycle is in the second one

V = 7, edges [[0,1],[1,2],[1,3],[4,5],[5,6],[6,4]] → graph: 0:[1] · 1:[0,2,3] · 2:[1] · 3:[1] · 4:[5,6] · 5:[4,6] · 6:[5,4].

  piece A (no cycle)        piece B (triangle)
  (0)—(1)—(2)               (4)———(5)
       |                      \   /
      (3)                      (6)

Piece A alone would give False. Only because the outer loop also starts at 4 do we find the triangle. That's the whole reason for Rule 3.

9Complexity & remember

• Time O(V + 2E). Each node gets one DFS call (V calls in total, because visited nodes are never called again). Inside the calls, the for loops run once per entry of the adjacency list. Every edge sits in two lists, so the total number of entries is the sum of all degrees, which is 2E. The loops are not "V × something": all of them together run 2E times. The teacher adds: here V and E are about the same size, so this is about 3V, which is linear (we drop the constant).
• Space O(V + 2E): the adjacency list holds V lists with 2E entries. Plus O(V) for visited, plus O(V) for the call stack in the worst case: with no cycle, a long line graph puts every node on the stack at once.

Part B · The same idea with an explicit stack

Not from the video, but useful in Python: if V is 10⁵ and the graph is one long line, the recursive version goes 10⁵ calls deep. Raising the recursion limit usually works, but on some machines a very deep recursion can still crash. Here is the same parent rule without recursion.

1What stays the same, what changes

• Same: the adjacency list, the outer loop over unvisited nodes, the rule "visited and not my parent → cycle".
• Changes: we keep our own list stack of (node, parent) pairs, and we mark a node visited when we push it, not when we pop it.

2Code (Python)

class Solution:
    def isCycle(self, V, edges):
        graph = [[] for _ in range(V)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = [False] * V
        for start in range(V):
            if visited[start]:
                continue
            visited[start] = True
            stack = [(start, -1)]          # (node, parent)
            while stack:
                node, parent = stack.pop()
                for nb in graph[node]:
                    if not visited[nb]:
                        visited[nb] = True     # mark when pushing
                        stack.append((nb, node))
                    elif nb != parent:
                        return True
        return False

3Complexity

Same as Part A: O(V + 2E) time and space. The stack replaces the call stack, and lives in normal memory, so depth is never a problem.

Part C · Revision page

s = Solution()
print(s.isCycle(4, [[0, 1], [0, 2], [1, 2], [2, 3]]))               # True
print(s.isCycle(4, [[0, 1], [1, 2], [2, 3]]))                       # False
print(s.isCycle(2, [[0, 1]]))                                       # False
print(s.isCycle(7, [[0, 1], [1, 2], [1, 3], [4, 5], [5, 6], [6, 4]]))  # True
print(s.isCycle(5, []))                                             # False

Based on this video: Detect Cycle in an Undirected Graph using DFS