Challenge - 5 Problems
Cycle Detection Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of cycle detection on a simple graph
What is the output of the following Rust code that detects a cycle in an undirected graph?
DSA Rust
use std::collections::HashMap;
use std::collections::HashSet;
fn dfs(
node: usize,
parent: Option<usize>,
graph: &HashMap<usize, Vec<usize>>,
visited: &mut HashSet<usize>,
) -> bool {
visited.insert(node);
for &neighbor in graph.get(&node).unwrap_or(&Vec::new()) {
if !visited.contains(&neighbor) {
if dfs(neighbor, Some(node), graph, visited) {
return true;
}
} else if Some(neighbor) != parent {
return true;
}
}
false
}
fn has_cycle(graph: &HashMap<usize, Vec<usize>>) -> bool {
let mut visited = HashSet::new();
for &node in graph.keys() {
if !visited.contains(&node) {
if dfs(node, None, graph, &mut visited) {
return true;
}
}
}
false
}
fn main() {
let mut graph = HashMap::new();
graph.insert(1, vec![2]);
graph.insert(2, vec![1, 3]);
graph.insert(3, vec![2, 4]);
graph.insert(4, vec![3, 1]);
println!("{}", has_cycle(&graph));
}Attempts:
2 left
💡 Hint
Think about whether the graph contains a loop connecting nodes back to an earlier node.
✗ Incorrect
The graph has edges forming a cycle: 1 - 2 - 3 - 4 - 1. The DFS detects this cycle and returns true.
❓ Predict Output
intermediate2:00remaining
Cycle detection output on a tree structure
What does the following Rust code print when checking for a cycle in a tree (acyclic graph)?
DSA Rust
use std::collections::{HashMap, HashSet};
fn dfs(
node: usize,
parent: Option<usize>,
graph: &HashMap<usize, Vec<usize>>,
visited: &mut HashSet<usize>,
) -> bool {
visited.insert(node);
for &neighbor in graph.get(&node).unwrap_or(&Vec::new()) {
if !visited.contains(&neighbor) {
if dfs(neighbor, Some(node), graph, visited) {
return true;
}
} else if Some(neighbor) != parent {
return true;
}
}
false
}
fn has_cycle(graph: &HashMap<usize, Vec<usize>>) -> bool {
let mut visited = HashSet::new();
for &node in graph.keys() {
if !visited.contains(&node) {
if dfs(node, None, graph, &mut visited) {
return true;
}
}
}
false
}
fn main() {
let mut graph = HashMap::new();
graph.insert(1, vec![2, 3]);
graph.insert(2, vec![1]);
graph.insert(3, vec![1, 4]);
graph.insert(4, vec![3]);
println!("{}", has_cycle(&graph));
}Attempts:
2 left
💡 Hint
A tree has no cycles by definition.
✗ Incorrect
The graph is a tree structure with no cycles. The DFS traversal finds no back edges, so it returns false.
🔧 Debug
advanced2:30remaining
Identify the error causing incorrect cycle detection
The following Rust code is intended to detect cycles in an undirected graph but always returns false even when a cycle exists. What is the bug?
DSA Rust
use std::collections::{HashMap, HashSet};
fn dfs(
node: usize,
parent: usize,
graph: &HashMap<usize, Vec<usize>>,
visited: &mut HashSet<usize>,
) -> bool {
visited.insert(node);
for &neighbor in graph.get(&node).unwrap_or(&Vec::new()) {
if !visited.contains(&neighbor) {
if dfs(neighbor, node, graph, visited) {
return true;
}
} else if neighbor != parent {
return true;
}
}
false
}
fn has_cycle(graph: &HashMap<usize, Vec<usize>>) -> bool {
let mut visited = HashSet::new();
for &node in graph.keys() {
if !visited.contains(&node) {
if dfs(node, 0, graph, &mut visited) {
return true;
}
}
}
false
}
fn main() {
let mut graph = HashMap::new();
graph.insert(1, vec![2]);
graph.insert(2, vec![1, 3]);
graph.insert(3, vec![2, 1]);
println!("{}", has_cycle(&graph));
}Attempts:
2 left
💡 Hint
Check how the parent node is passed for the first DFS call.
✗ Incorrect
The DFS function uses a parent parameter of type usize, but the first call passes 0 as parent, which may be a valid node. This causes incorrect cycle detection logic. Using Option
❓ Predict Output
advanced2:00remaining
Output of cycle detection on disconnected graph with one cycle
What is the output of the following Rust code detecting cycles in a disconnected undirected graph where only one component has a cycle?
DSA Rust
use std::collections::{HashMap, HashSet};
fn dfs(
node: usize,
parent: Option<usize>,
graph: &HashMap<usize, Vec<usize>>,
visited: &mut HashSet<usize>,
) -> bool {
visited.insert(node);
for &neighbor in graph.get(&node).unwrap_or(&Vec::new()) {
if !visited.contains(&neighbor) {
if dfs(neighbor, Some(node), graph, visited) {
return true;
}
} else if Some(neighbor) != parent {
return true;
}
}
false
}
fn has_cycle(graph: &HashMap<usize, Vec<usize>>) -> bool {
let mut visited = HashSet::new();
for &node in graph.keys() {
if !visited.contains(&node) {
if dfs(node, None, graph, &mut visited) {
return true;
}
}
}
false
}
fn main() {
let mut graph = HashMap::new();
// Component 1 (no cycle)
graph.insert(1, vec![2]);
graph.insert(2, vec![1]);
// Component 2 (cycle: 3-4-5-3)
graph.insert(3, vec![4, 5]);
graph.insert(4, vec![3, 5]);
graph.insert(5, vec![3, 4]);
println!("{}", has_cycle(&graph));
}Attempts:
2 left
💡 Hint
Check if the algorithm detects cycles in any connected component.
✗ Incorrect
The graph has two components. The second component contains a cycle among nodes 3, 4, and 5. The function returns true.
🧠 Conceptual
expert1:30remaining
Why does DFS use a parent parameter in cycle detection for undirected graphs?
In cycle detection for undirected graphs using DFS, why is it necessary to pass the parent node to the DFS function?
Attempts:
2 left
💡 Hint
Think about why revisiting the immediate previous node should not count as a cycle.
✗ Incorrect
In undirected graphs, each edge is bidirectional. Without the parent parameter, the DFS would detect the edge back to the parent as a cycle. Passing the parent node helps ignore this edge.