Cycle Detection in Undirected Graph in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to add an edge between two nodes in the undirected graph.

DSA Rust

graph[[1]].push(v);
graph[v].push(u);

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

A0

Bv

Cu

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong node index for the adjacency list.

Forgetting to add the edge in both directions.

The edge is added from node u to v and vice versa because the graph is undirected.

2fill in blank

medium

Complete the code to mark the current node as visited during DFS.

DSA Rust

visited[[1]] = true;

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

Aparent

Bnode

Cneighbor

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Marking the parent node instead of the current node.

Marking a neighbor before visiting it.

We mark the current node as visited to avoid revisiting it.

3fill in blank

hard

Fix the error in the DFS condition to detect a cycle when a visited neighbor is not the parent.

DSA Rust

if visited[neighbor] && neighbor != [1] {
    return true;
}

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

Aparent

Bnode

Cvisited

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing neighbor with the current node instead of parent.

Not checking if the neighbor is visited.

The cycle is detected if a visited neighbor is not the parent of the current node.

4fill in blank

hard

Fill both blanks to complete the DFS recursive call and cycle check.

DSA Rust

if !visited[[1]] {
    if dfs(graph, visited, [2], node) {
        return true;
    }
}

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

Aneighbor

Bnode

Cparent

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong variable for the next node.

Passing the wrong parent node in recursion.

We recurse DFS on the neighbor node, passing the current node as its parent.

5fill in blank

hard

Fill all three blanks to complete the cycle detection function that iterates over all nodes.

DSA Rust

for i in 0..graph.len() {
    if !visited[[1]] {
        if dfs(&graph, &mut visited, [2], [3]) {
            return true;
        }
    }
}
return false;

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

Ai

Cusize::MAX

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices for visited array.

Passing incorrect parent value in DFS call.

We check each node i if unvisited, call DFS with i and usize::MAX as parent (no parent).

Practice

1. What is the main idea behind detecting a cycle in an undirected graph using DFS?

easy

A. If we visit a node that is already visited and is not the parent, a cycle exists.

B. If all nodes are visited exactly once, the graph has a cycle.

C. If the graph has more edges than nodes, it must have a cycle.

D. If the graph is disconnected, it contains a cycle.

Solution

1. Step 1: Understand DFS traversal in undirected graph

   DFS visits nodes and tracks the parent node to avoid false cycle detection.

2. Step 2: Detect cycle condition

   If a visited node is found that is not the parent, it means a back edge exists, indicating a cycle.

3. Final Answer:

   If we visit a node that is already visited and is not the parent, a cycle exists. -> Option A

4. Quick Check:

   Cycle detection in undirected graph = check visited & parent [OK]

Hint: Check visited nodes excluding parent during DFS to find cycles [OK]

Common Mistakes:

• Ignoring the parent node when checking visited nodes
• Assuming disconnected graph always has cycles
• Confusing cycle detection logic with directed graphs
• Counting edges vs nodes incorrectly

2. Which Rust code snippet correctly initializes an adjacency list for an undirected graph with 3 nodes?

easy

A. let graph = vec![vec![]; 3]; graph[0].push(1); graph[1].push(0); graph[1].push(2); graph[2].push(1);

B. let mut graph = vec![vec![]; 3]; graph[0].push(1); graph[1].push(0); graph[1].push(2); graph[2].push(1);

C. let mut graph = vec![vec![]; 3]; graph[0].push(1); graph[1].push(2); graph[2].push(1);

D. let mut graph = vec![vec![]; 3]; graph[0].push(1); graph[1].push(0); graph[2].push(1);

Solution

1. Step 1: Initialize mutable adjacency list

   Use let mut graph = vec![vec![]; 3]; to create a mutable vector of vectors for 3 nodes.

2. Step 2: Add edges for undirected graph

   For each edge, add both directions: node 0 to 1 and node 1 to 0, node 1 to 2 and node 2 to 1.

3. Final Answer:

   let mut graph = vec![vec![]; 3]; graph[0].push(1); graph[1].push(0); graph[1].push(2); graph[2].push(1); -> Option B

4. Quick Check:

   Mutable adjacency list with bidirectional edges = correct initialization [OK]

Hint: Use 'mut' and push edges both ways for undirected graph [OK]

Common Mistakes:

• Forgetting 'mut' keyword for mutable vector
• Adding edges only one way in undirected graph
• Trying to push to immutable vector
• Incorrect vector initialization syntax

3. What will be the output of the following Rust code snippet detecting cycle in an undirected graph?

fn dfs(node: usize, parent: usize, graph: &Vec, visited: &mut Vec<bool>) -> bool {
    visited[node] = true;
    for &neighbor in &graph[node] {
        if !visited[neighbor] {
            if dfs(neighbor, node, graph, visited) {
                return true;
            }
        } else if neighbor != parent {
            return true;
        }
    }
    false
}

fn main() {
    let mut graph = vec![vec![]; 4];
    graph[0].push(1); graph[1].push(0);
    graph[1].push(2); graph[2].push(1);
    graph[2].push(3); graph[3].push(2);
    graph[3].push(1); graph[1].push(3);

    let mut visited = vec![false; 4];
    let has_cycle = dfs(0, usize::MAX, &graph, &mut visited);
    println!("{}", has_cycle);
}

medium

A. Runtime panic

B. false

C. true

D. Compilation error

Solution

1. Step 1: Analyze graph edges and structure

   The graph edges form a cycle: 1-2-3-1, so cycle exists.

2. Step 2: Trace DFS cycle detection logic

   DFS visits nodes and finds a visited neighbor (1) not equal to parent, returning true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Cycle detected in DFS = true [OK]

Hint: Look for back edges to visited nodes excluding parent [OK]

Common Mistakes:

• Ignoring the edge from 3 to 1 forming a cycle
• Confusing parent node with visited node
• Assuming no cycle if start node is 0
• Misreading DFS return conditions

4. Identify the bug in this Rust DFS cycle detection code for an undirected graph:

fn dfs(node: usize, parent: usize, graph: &Vec, visited: &mut Vec<bool>) -> bool {
    visited[node] = true;
    for &neighbor in &graph[node] {
        if visited[neighbor] {
            if neighbor != parent {
                return true;
            }
        } else {
            dfs(neighbor, node, graph, visited);
        }
    }
    false
}

medium

A. Missing return statement for recursive dfs call

B. Incorrect parent check condition

C. Visited vector should be immutable

D. Graph should be mutable

Solution

1. Step 1: Check recursive call usage

   The recursive call to dfs is made but its result is ignored, missing return propagation.

2. Step 2: Fix by returning recursive call result

   Return the result of dfs(neighbor, node, graph, visited) to propagate cycle detection upwards.

3. Final Answer:

   Missing return statement for recursive dfs call -> Option A

4. Quick Check:

   Return recursive dfs result to detect cycles correctly [OK]

Hint: Always return recursive call result in DFS for cycle detection [OK]

Common Mistakes:

• Ignoring return value of recursive DFS calls
• Confusing parent check logic
• Using immutable visited vector incorrectly
• Assuming graph mutability is required here

5. Given an undirected graph represented as adjacency list in Rust, how can you modify the DFS cycle detection to handle disconnected graphs and detect cycles in all components? Choose the best approach.

hard

A. Use BFS instead of DFS for cycle detection.

B. Run DFS only from node 0, assuming graph is connected.

C. Mark all nodes visited initially and then run DFS once.

D. Run DFS from every unvisited node in a loop to cover all components.

Solution

1. Step 1: Understand disconnected graph scenario

   Disconnected graphs have multiple components; DFS from one node covers only one component.

2. Step 2: Modify DFS to run on all components

   Loop over all nodes, run DFS if node is unvisited to detect cycles in every component.

3. Final Answer:

   Run DFS from every unvisited node in a loop to cover all components. -> Option D

4. Quick Check:

   Cycle detection in disconnected graph = DFS from all unvisited nodes [OK]

Hint: Loop DFS over all nodes to cover disconnected components [OK]

Common Mistakes:

• Assuming graph is always connected
• Running DFS only once from node 0
• Using BFS without cycle detection logic
• Marking all nodes visited before DFS