Cycle Detection in Undirected Graph in DSA Rust - Time & Space Complexity

Time Complexity: Cycle Detection in Undirected Graph

O(n + m)

Understanding Time Complexity

We want to understand how long it takes to find a cycle in an undirected graph.

Specifically, how the time grows as the graph gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code uses depth-first search to check if a cycle exists by visiting nodes and tracking parents.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive DFS visits each node and its neighbors.
• How many times: Each edge and node is checked once during the traversal.

How Execution Grows With Input

As the graph grows, the DFS visits more nodes and edges.

Input Size (n nodes, m edges)	Approx. Operations
10 nodes, 15 edges	About 25 checks (nodes + edges)
100 nodes, 200 edges	About 300 checks
1000 nodes, 3000 edges	About 4000 checks

Pattern observation: The work grows roughly with the number of nodes plus edges.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows linearly with the total nodes and edges in the graph.

Common Mistake

[X] Wrong: "The DFS checks every possible path, so it takes exponential time."

[OK] Correct: DFS visits each node and edge only once, so it does not repeat work exponentially.

Interview Connect

Understanding this time complexity helps you explain how graph traversal scales and why DFS is efficient for cycle detection.

Self-Check

"What if the graph was directed instead of undirected? How would the time complexity change?"

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