Cycle Detection in Directed Graph in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the visited list for all nodes.

DSA Python

visited = [False] * [1]

Drag options to blanks, or click blank then click option'

Alen(graph)

Bgraph

Clen(graph) + 1

Drange(len(graph))

Attempts:

3 left

💡 Hint

Common Mistakes

Using the graph object directly instead of its length

Using range object instead of length

The visited list should have one entry per node, so its length must be the number of nodes, which is len(graph).

2fill in blank

medium

Complete the code to mark the current node as visited in the DFS function.

DSA Python

visited[node] = [1]

Drag options to blanks, or click blank then click option'

ANone

BFalse

CTrue

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited as False

Assigning None instead of True

When visiting a node, we mark it as True in the visited list to indicate it has been visited.

3fill in blank

hard

Fix the error in the condition to detect a cycle when a node is in the recursion stack.

DSA Python

if rec_stack[neighbor] == [1]:

Drag options to blanks, or click blank then click option'

ATrue

BNone

CFalse

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for False instead of True

Using None or 0 incorrectly

A cycle is detected if a neighbor is already in the recursion stack, which means rec_stack[neighbor] is True.

4fill in blank

hard

Fill both blanks to correctly update the recursion stack when entering and leaving a node.

DSA Python

rec_stack[node] = [1]
...
rec_stack[node] = [2]

Drag options to blanks, or click blank then click option'

ATrue

BFalse

CNone

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Not resetting the recursion stack to False

Using None or 0 instead of booleans

When entering a node, mark it True in the recursion stack. When leaving, mark it False.

5fill in blank

hard

Fill all three blanks to complete the DFS function header and the loop over neighbors.

DSA Python

def dfs([1], graph, visited, rec_stack):
    visited[node] = True
    rec_stack[node] = True
    for [2] in graph[node]:
        if not visited[neighbor]:
            if dfs([3], graph, visited, rec_stack):
                return True
    rec_stack[node] = False
    return False

Drag options to blanks, or click blank then click option'

Anode

Bneighbor

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing variable names between node and neighbor

Using wrong variable in recursive call

The DFS function takes node as the current node. The loop variable is neighbor. The recursive call uses neighbor as the current node argument.

Specifically: def dfs(node, ...), for neighbor in graph[node], and dfs(neighbor, ...).

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