Cycle Detection in Directed Graph in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection using DFS

What is the output of the following code that detects a cycle in a directed graph using DFS?

DSA Python

def dfs(node, graph, visited, rec_stack):
    visited.add(node)
    rec_stack.add(node)
    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            if dfs(neighbor, graph, visited, rec_stack):
                return True
        elif neighbor in rec_stack:
            return True
    rec_stack.remove(node)
    return False

graph = {0: [1], 1: [2], 2: [0, 3], 3: []}
visited = set()
rec_stack = set()
result = any(dfs(node, graph, visited, rec_stack) for node in graph if node not in visited)
print(result)

A False

B None

C KeyError

D True

💡 Hint

Think about whether the graph contains a back edge that forms a cycle.

The graph has a cycle: 0 -> 1 -> 2 -> 0. The DFS detects this cycle and returns True.

❓ Predict Output

intermediate

Output of cycle detection using colors

What is the output of this code that uses colors (0=unvisited, 1=visiting, 2=visited) to detect a cycle in a directed graph?

DSA Python

def dfs(node, graph, color):
    if color[node] == 1:
        return True
    if color[node] == 2:
        return False
    color[node] = 1
    for neighbor in graph.get(node, []):
        if dfs(neighbor, graph, color):
            return True
    color[node] = 2
    return False

graph = {0: [1], 1: [2], 2: [3], 3: []}
color = {node: 0 for node in graph}
result = any(dfs(node, graph, color) for node in graph)
print(result)

A False

B TypeError

C True

D KeyError

💡 Hint

Check if any node is revisited while still being visited (color 1).

The graph is a straight chain with no cycles, so the output is False.

🔧 Debug

advanced

Identify the error in cycle detection code

What error does the following code raise when detecting cycles in a directed graph?

DSA Python

def dfs(node, graph, visited, rec_stack):
    visited.add(node)
    rec_stack.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            if dfs(neighbor, graph, visited, rec_stack):
                return True
        elif neighbor in rec_stack:
            return True
    rec_stack.remove(node)
    return False

graph = {0: [1], 1: [2], 2: [3]}
visited = set()
rec_stack = set()
result = any(dfs(node, graph, visited, rec_stack) for node in range(4) if node not in visited)
print(result)

A IndexError

B KeyError

C TypeError

D No error, prints False

💡 Hint

Check the nodes used in the loop and keys in the graph dictionary.

Node 3 is not a key in the graph dictionary, so graph[3] raises a KeyError.

🚀 Application

advanced

Number of cycles in a directed graph

Given the graph below, how many distinct cycles does it contain?

DSA Python

graph = {0: [1], 1: [2, 3], 2: [0], 3: [4], 4: [1]}

A 2

B 1

C 3

D 0

💡 Hint

Look for all paths that start and end at the same node without repetition.

There are two cycles: 0->1->2->0 and 1->3->4->1.

🧠 Conceptual

expert

Why does DFS detect cycles in directed graphs but not always in undirected graphs?

Which statement best explains why DFS cycle detection differs between directed and undirected graphs?

A In directed graphs, back edges indicate cycles; in undirected graphs, any visited edge is a cycle.

B In undirected graphs, DFS cannot detect cycles because edges are bidirectional.

C In directed graphs, DFS uses recursion stack to detect back edges; in undirected graphs, parent tracking is needed to avoid false positives.

D Cycle detection is identical in both graph types using DFS without any modification.

💡 Hint

Consider how edges are treated differently in directed vs undirected graphs during DFS.

In directed graphs, a back edge to a node in the recursion stack indicates a cycle. In undirected graphs, edges are bidirectional, so DFS must track the parent node to avoid mistaking the immediate parent edge as a cycle.

Practice

1. What does cycle detection in a directed graph help us find?

easy

A. The total number of nodes in the graph

B. The shortest path between two nodes

C. The maximum degree of any node

D. Whether there is a path that starts and ends at the same node following the direction of edges

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means starting from a node and following directed edges, you can return to the same node.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists in the graph.

3. Final Answer:

   Whether there is a path that starts and ends at the same node following the direction of edges -> Option D

4. Quick Check:

   Cycle detection = path returning to start node [OK]

Hint: Cycle means path loops back to start node following edges [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Ignoring edge directions
• Thinking cycle means any repeated node without direction

2. Which Python data structure is commonly used to keep track of nodes currently in the recursion stack during cycle detection in a directed graph?

easy

A. Set

B. List

C. Dictionary

D. Queue

Solution

1. Step 1: Identify recursion stack tracking

   During DFS, nodes currently being explored are tracked to detect cycles.

2. Step 2: Choose data structure for fast membership check

   Set allows O(1) check if a node is in recursion stack.

3. Final Answer:

   Set -> Option A

4. Quick Check:

   Recursion stack uses set for fast lookup [OK]

Hint: Use set for fast check if node is in recursion stack [OK]

Common Mistakes:

• Using list which is slower for membership check
• Using queue which is FIFO, not suitable here
• Using dictionary without keys for membership

3. What will be the output of the following code snippet?

graph = {0: [1], 1: [2], 2: [0]}
visited = set()
rec_stack = set()
def dfs(node):
    if node in rec_stack:
        return True
    if node in visited:
        return False
    visited.add(node)
    rec_stack.add(node)
    for neighbor in graph.get(node, []):
        if dfs(neighbor):
            return True
    rec_stack.remove(node)
    return False

print(dfs(0))

medium

A. True

B. False

C. None

D. Error

Solution

1. Step 1: Trace DFS calls starting from node 0

   Node 0 calls dfs(1), which calls dfs(2), which calls dfs(0) again.

2. Step 2: Detect cycle when node 0 is in recursion stack

   When dfs(0) is called second time, node 0 is in rec_stack, so returns True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Cycle detected = True [OK]

Hint: Cycle if node revisited in recursion stack returns True [OK]

Common Mistakes:

• Ignoring recursion stack check
• Confusing visited with recursion stack
• Assuming no cycle returns True

4. Find the bug in this cycle detection code snippet for a directed graph:

def dfs(node, graph, visited, rec_stack):
    visited.add(node)
    rec_stack.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, graph, visited, rec_stack)
        elif neighbor in rec_stack:
            return True
    rec_stack.remove(node)
    return False

medium

A. Should use list instead of set for rec_stack

B. Missing return value when dfs(neighbor) is called recursively

C. Visited set should be cleared after recursion

D. Graph keys should be integers only

Solution

1. Step 1: Check recursive call return usage

   The recursive call dfs(neighbor, ...) is made but its return value is ignored.

2. Step 2: Fix by returning True if recursive call finds cycle

   Should return True immediately if dfs(neighbor, ...) returns True.

3. Final Answer:

   Missing return value when dfs(neighbor) is called recursively -> Option B

4. Quick Check:

   Return True on recursive cycle detection [OK]

Hint: Return True immediately when recursive call detects cycle [OK]

Common Mistakes:

• Ignoring recursive call return value
• Using wrong data structure for rec_stack
• Clearing visited incorrectly

5. Given a directed graph represented as adjacency list:

graph = {
  'A': ['B'],
  'B': ['C', 'D'],
  'C': ['E'],
  'D': ['F'],
  'E': ['B'],
  'F': []
}

Which nodes are part of at least one cycle?

hard

A. A, D, F

B. A, B, C, E

C. B, C, E

D. No nodes form a cycle

Solution

1. Step 1: Identify cycles by tracing edges

   Path B -> C -> E -> B forms a cycle involving B, C, E.

2. Step 2: Check other nodes

   A leads to B but is not in cycle; D and F have no cycles.

3. Final Answer:

   B, C, E -> Option C

4. Quick Check:

   Cycle nodes = B, C, E [OK]

Hint: Trace edges to find nodes revisited in cycle [OK]

Common Mistakes:

• Including nodes only leading to cycle but not in it
• Ignoring indirect cycles
• Assuming all connected nodes form cycles