Cycle detection in graphs in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a graph has a cycle using DFS.

Data Structures Theory

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

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

Arec_stack

Bvisited

Cgraph

Dstack

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if neighbor is in visited instead of recursion stack.

Not removing node from recursion stack after DFS call.

The recursion stack rec_stack keeps track of nodes currently in the recursion path. If a neighbor is already in rec_stack, it means a cycle exists.

2fill in blank

medium

Complete the code to initialize the visited set before DFS traversal.

Data Structures Theory

visited = set()
for node in graph:
    if node not in [1]:
        if dfs(node, visited, set()):
            print("Cycle detected")

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

Avisited

Brec_stack

Cstack

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Checking membership in recursion stack instead of visited.

Starting DFS on all nodes without checking visited.

We check if a node is not in the visited set before starting DFS to avoid repeated work.

3fill in blank

hard

Fix the error in the cycle detection condition inside DFS.

Data Structures Theory

if neighbor in visited and neighbor in [1]:
    return True

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

Avisited

Brec_stack

Cgraph

Dstack

Attempts:

3 left

💡 Hint

Common Mistakes

Checking only visited set for cycle detection.

Confusing recursion stack with visited set.

The cycle is detected if the neighbor is in the recursion stack, not just visited. So the condition should check rec_stack.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps each node to its neighbors count and filters nodes with more than 2 neighbors.

Data Structures Theory

neighbor_counts = {node: len(graph[node]) for node in graph if len(graph[node]) [1] [2]

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

A>

B2

C<

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using less than or equal instead of greater than.

Confusing the order of operator and number.

The comprehension counts neighbors and filters nodes with more than 2 neighbors using > 2.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps uppercase node names to their neighbor count, filtering nodes with at least 1 neighbor.

Data Structures Theory

result = { [1]: len(graph[node]) for node in graph if len(graph[node]) [2] [3]

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

Anode.upper()

B>=

C1

Dnode.lower()

Attempts:

3 left

💡 Hint

Common Mistakes

Using lowercase instead of uppercase for node names.

Using less than instead of greater than or equal for filtering.

The comprehension maps uppercase node names (node.upper()) to neighbor counts, filtering nodes with at least one neighbor (>= 1).