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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection on a simple directed graph

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

DSA Rust

use std::collections::HashMap;
use std::collections::HashSet;

fn has_cycle(
    node: usize,
    graph: &HashMap<usize, Vec<usize>>,
    visited: &mut HashSet<usize>,
    stack: &mut HashSet<usize>,
) -> bool {
    if stack.contains(&node) {
        return true;
    }
    if visited.contains(&node) {
        return false;
    }
    visited.insert(node);
    stack.insert(node);
    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            if has_cycle(neighbor, graph, visited, stack) {
                return true;
            }
        }
    }
    stack.remove(&node);
    false
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(1, vec![2]);
    graph.insert(2, vec![3]);
    graph.insert(3, vec![4]);
    graph.insert(4, vec![2]);

    let mut visited = HashSet::new();
    let mut stack = HashSet::new();

    let result = has_cycle(1, &graph, &mut visited, &mut stack);
    println!("{}", result);
}

A Compilation error

B false

C true

D Runtime panic

💡 Hint

Trace the recursion and check if the function detects a back edge in the graph.

The graph has a cycle: 2 -> 3 -> 4 -> 2. The function detects this cycle and returns true.

❓ Predict Output

intermediate

Output of cycle detection on an acyclic directed graph

What is the output of the following Rust code that detects a cycle in a directed graph without cycles?

DSA Rust

use std::collections::HashMap;
use std::collections::HashSet;

fn has_cycle(
    node: usize,
    graph: &HashMap<usize, Vec<usize>>,
    visited: &mut HashSet<usize>,
    stack: &mut HashSet<usize>,
) -> bool {
    if stack.contains(&node) {
        return true;
    }
    if visited.contains(&node) {
        return false;
    }
    visited.insert(node);
    stack.insert(node);
    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            if has_cycle(neighbor, graph, visited, stack) {
                return true;
            }
        }
    }
    stack.remove(&node);
    false
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(1, vec![2]);
    graph.insert(2, vec![3]);
    graph.insert(3, vec![4]);
    graph.insert(4, vec![]);

    let mut visited = HashSet::new();
    let mut stack = HashSet::new();

    let result = has_cycle(1, &graph, &mut visited, &mut stack);
    println!("{}", result);
}

A false

B true

C Compilation error

D Runtime panic

💡 Hint

Check if any node is revisited while still in the recursion stack.

The graph has no cycles, so the function returns false.

🔧 Debug

advanced

Identify the error in cycle detection code

What error does the following Rust code produce when detecting a cycle in a directed graph?

DSA Rust

use std::collections::HashMap;
use std::collections::HashSet;

fn has_cycle(
    node: usize,
    graph: &HashMap<usize, Vec<usize>>,
    visited: &mut HashSet<usize>,
    stack: &mut HashSet<usize>,
) -> bool {
    if stack.contains(&node) {
        return true;
    }
    if visited.contains(&node) {
        return false;
    }
    visited.insert(node);
    stack.insert(node);
    if let Some(neighbors) = graph.get(&node) {
        for neighbor in neighbors {
            if has_cycle(*neighbor, graph, visited, stack) {
                return true;
            }
        }
    }
    stack.remove(&node);
    false
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(1, vec![2]);
    graph.insert(2, vec![3]);
    graph.insert(3, vec![1]);

    let mut visited = HashSet::new();
    let mut stack = HashSet::new();

    let result = has_cycle(1, &graph, &mut visited, &mut stack);
    println!("{}", result);
}

A Prints true

B Compilation error due to dereferencing in for loop

C Runtime panic due to stack overflow

D Prints false

💡 Hint

Check how neighbors are accessed and dereferenced in the loop.

The code correctly detects the cycle 1 -> 2 -> 3 -> 1 and prints true.

🧠 Conceptual

advanced

Why use a recursion stack in cycle detection?

In cycle detection for directed graphs, why do we use a recursion stack (or call stack tracking) alongside a visited set?

A To count the total number of nodes in the graph

B To keep track of all visited nodes to avoid revisiting

C To store the order of nodes for topological sorting

D To detect back edges indicating a cycle during DFS traversal

💡 Hint

Think about what a back edge means in a directed graph DFS.

The recursion stack helps detect back edges, which indicate cycles in directed graphs.

🚀 Application

expert

Number of nodes in cycle detected by algorithm

Given the following directed graph and cycle detection code, how many nodes are part of the detected cycle?

DSA Rust

use std::collections::{HashMap, HashSet};

fn find_cycle_nodes(
    node: usize,
    graph: &HashMap<usize, Vec<usize>>,
    visited: &mut HashSet<usize>,
    stack: &mut Vec<usize>,
    cycle_nodes: &mut HashSet<usize>,
) -> bool {
    if stack.contains(&node) {
        let pos = stack.iter().position(|&x| x == node).unwrap();
        for &n in &stack[pos..] {
            cycle_nodes.insert(n);
        }
        return true;
    }
    if visited.contains(&node) {
        return false;
    }
    visited.insert(node);
    stack.push(node);
    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            if find_cycle_nodes(neighbor, graph, visited, stack, cycle_nodes) {
                return true;
            }
        }
    }
    stack.pop();
    false
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(1, vec![2]);
    graph.insert(2, vec![3, 4]);
    graph.insert(3, vec![1]);
    graph.insert(4, vec![5]);
    graph.insert(5, vec![]);

    let mut visited = HashSet::new();
    let mut stack = Vec::new();
    let mut cycle_nodes = HashSet::new();

    find_cycle_nodes(1, &graph, &mut visited, &mut stack, &mut cycle_nodes);
    println!("{}", cycle_nodes.len());
}

A 2

B 3

C 5

D 4

💡 Hint

Identify the cycle nodes from the graph edges and the recursion stack slice.

The cycle is 1 -> 2 -> 3 -> 1, so 3 nodes are in the cycle.

Practice

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

easy

A. If the graph has any isolated nodes

B. If the graph has equal number of nodes and edges

C. If the graph is fully connected

D. If 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 at a node and following edges in their direction to come back 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:

   If 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 starting and ending at same node [OK]

Hint: Cycle means a path back to start following edge directions [OK]

Common Mistakes:

• Confusing cycle with connectivity
• Thinking cycle ignores edge directions
• Assuming cycle means isolated nodes

2. Which Rust data structure is best to keep track of nodes currently in the recursion stack during DFS for cycle detection?

easy

A. HashSet<i32>

B. Vec<bool>

C. Vec<i32>

D. HashMap

Solution

1. Step 1: Identify purpose of recursion stack tracking

   We need to mark nodes currently being explored to detect back edges indicating cycles.

2. Step 2: Choose data structure for boolean tracking

   Vec<bool> is efficient to mark true/false for each node index during DFS recursion.

3. Final Answer:

   Vec<bool> -> Option B

4. Quick Check:

   Use Vec<bool> to track recursion stack nodes [OK]

Hint: Use boolean vector to mark recursion stack nodes [OK]

Common Mistakes:

• Using HashMap when simple Vec<bool> suffices
• Using Vec<i32> which stores values, not boolean flags
• Using HashSet which is less efficient here

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

fn main() {
    let graph = vec![
        vec![1],    // 0 -> 1
        vec![2],    // 1 -> 2
        vec![0],    // 2 -> 0 forms a cycle
        vec![4],    // 3 -> 4
        vec![]      // 4 no outgoing edges
    ];
    println!("{}", has_cycle(&graph));
}

fn has_cycle(graph: &Vec) -> bool {
    let n = graph.len();
    let mut visited = vec![false; n];
    let mut rec_stack = vec![false; n];

    for node in 0..n {
        if !visited[node] && dfs(node, graph, &mut visited, &mut rec_stack) {
            return true;
        }
    }
    false
}

fn dfs(node: usize, graph: &Vec, visited: &mut Vec<bool>, rec_stack: &mut Vec<bool>) -> bool {
    visited[node] = true;
    rec_stack[node] = true;

    for &neighbor in &graph[node] {
        if !visited[neighbor] && dfs(neighbor, graph, visited, rec_stack) {
            return true;
        } else if rec_stack[neighbor] {
            return true;
        }
    }

    rec_stack[node] = false;
    false
}

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Analyze graph edges for cycles

   Nodes 0->1, 1->2, 2->0 form a cycle because 2 points back to 0.

2. Step 2: Understand DFS cycle detection logic

   DFS marks nodes visited and tracks recursion stack. When it finds a neighbor in recursion stack, it returns true indicating cycle.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Cycle exists in 0->1->2->0 path = true [OK]

Hint: Cycle if DFS finds neighbor in recursion stack [OK]

Common Mistakes:

• Ignoring recursion stack check
• Assuming no cycle because graph is small
• Confusing visited with recursion stack

4. Identify the bug in this Rust DFS function for cycle detection in a directed graph:

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

medium

A. Function does not return a boolean

B. visited[node] is not set to true

C. rec_stack[node] is never set to true at start

D. Graph parameter type is incorrect

Solution

1. Step 1: Check recursion stack usage

   rec_stack[node] should be set to true when node is first visited to track recursion path.

2. Step 2: Identify missing line

   Code misses rec_stack[node] = true at start, so cycle detection via recursion stack fails.

3. Final Answer:

   rec_stack[node] is never set to true at start -> Option C

4. Quick Check:

   Set rec_stack[node] = true before DFS neighbors [OK]

Hint: Always mark node in recursion stack before DFS neighbors [OK]

Common Mistakes:

• Forgetting to mark recursion stack at start
• Confusing visited and recursion stack roles
• Not returning boolean properly

5. Given a directed graph represented as adjacency list:

let graph = vec![
    vec![1, 2],  // 0 -> 1, 0 -> 2
    vec![3],     // 1 -> 3
    vec![3],     // 2 -> 3
    vec![4],     // 3 -> 4
    vec![1]      // 4 -> 1 creates a cycle
];

Which nodes are part of the cycle detected by DFS cycle detection?

hard

A. [1, 3, 4]

B. [0, 1, 2]

C. [0, 4]

D. [2, 3, 4]

Solution

1. Step 1: Trace cycle path in graph

   Edges 1->3, 3->4, 4->1 form a cycle involving nodes 1, 3, and 4.

2. Step 2: Confirm nodes in cycle

   Node 0 and 2 are not in cycle because they lead into cycle but not part of cycle loop.

3. Final Answer:

   [1, 3, 4] -> Option A

4. Quick Check:

   Cycle nodes = 1, 3, 4 [OK]

Hint: Cycle nodes form closed loop edges [OK]

Common Mistakes:

• Including nodes that only lead to cycle
• Missing nodes that complete the cycle
• Confusing cycle with path