Bridges in Graph Tarjan's Algorithm in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tarjan's Algorithm for Bridges

What is the output (list of bridges) of the following Rust code implementing Tarjan's algorithm on the given graph?

DSA Rust

use std::collections::HashMap;

fn tarjan_bridges(
    u: usize,
    parent: Option<usize>,
    time: &mut usize,
    graph: &HashMap<usize, Vec<usize>>,
    disc: &mut Vec<Option<usize>>,
    low: &mut Vec<usize>,
    bridges: &mut Vec<(usize, usize)>,
) {
    *time += 1;
    disc[u] = Some(*time);
    low[u] = *time;

    if let Some(neighbors) = graph.get(&u) {
        for &v in neighbors {
            if disc[v].is_none() {
                tarjan_bridges(v, Some(u), time, graph, disc, low, bridges);
                low[u] = low[u].min(low[v]);
                if low[v] > disc[u].unwrap() {
                    bridges.push((u, v));
                }
            } else if Some(v) != parent {
                low[u] = low[u].min(disc[v].unwrap());
            }
        }
    }
}

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

    let n = 5;
    let mut disc = vec![None; n];
    let mut low = vec![0; n];
    let mut bridges = Vec::new();
    let mut time = 0;

    for i in 0..n {
        if disc[i].is_none() {
            tarjan_bridges(i, None, &mut time, &graph, &mut disc, &mut low, &mut bridges);
        }
    }

    bridges.sort();
    println!("{:?}", bridges);
}

A [(0, 1), (2, 3)]

B [(1, 2), (3, 4)]

C [(2, 3), (3, 4)]

D [(0, 2), (3, 4)]

💡 Hint

Look for edges where the low value of the neighbor is greater than the discovery time of the current node.

Edges (2,3) and (3,4) are bridges because removing them increases the number of connected components. The other edges are part of cycles.

🧠 Conceptual

intermediate

Understanding Low and Discovery Times

In Tarjan's algorithm for bridges, what does the 'low' value of a node represent?

A The earliest discovery time reachable from the node including back edges

B The total number of neighbors the node has

C The depth of the node in the DFS tree

D The number of bridges connected to the node

💡 Hint

Think about what 'low' helps to detect in the graph.

'Low' is the smallest discovery time reachable from the node by following tree edges and back edges, helping detect cycles and bridges.

🔧 Debug

advanced

Identify the Bug in Tarjan's Bridge Detection

What error will the following Rust code produce when running Tarjan's algorithm for bridges?

DSA Rust

fn tarjan(
    u: usize,
    parent: usize,
    time: &mut usize,
    graph: &Vec<Vec<usize>>,
    disc: &mut Vec<Option<usize>>,
    low: &mut Vec<usize>,
    bridges: &mut Vec<(usize, usize)>,
) {
    *time += 1;
    disc[u] = Some(*time);
    low[u] = *time;

    for &v in &graph[u] {
        if disc[v].is_none() {
            tarjan(v, u, time, graph, disc, low, bridges);
            low[u] = low[u].min(low[v]);
            if low[v] > disc[u].unwrap() {
                bridges.push((u, v));
            }
        } else if v != parent {
            low[u] = low[u].min(disc[v].unwrap());
        }
    }
}

fn main() {
    let graph = vec![
        vec![1, 2],
        vec![0, 2],
        vec![0, 1, 3],
        vec![2, 4],
        vec![3],
    ];
    let n = graph.len();
    let mut disc = vec![None; n];
    let mut low = vec![0; n];
    let mut bridges = Vec::new();
    let mut time = 0;

    for i in 0..n {
        if disc[i].is_none() {
            tarjan(i, usize::MAX, &mut time, &graph, &mut disc, &mut low, &mut bridges);
        }
    }

    bridges.sort();
    println!("{:?}", bridges);
}

A No error, outputs [(2, 3), (3, 4)]

B Panic due to unwrap on None value

C Stack overflow due to infinite recursion

D Compilation error due to usize::MAX used as parent

💡 Hint

Check how parent is handled and if usize::MAX causes issues.

Using usize::MAX as parent is valid since it never matches any node index. The code runs correctly and outputs the bridges.

❓ Predict Output

advanced

Output of Bridge Detection on a Complex Graph

What is the output list of bridges for the following graph using Tarjan's algorithm?

DSA Rust

use std::collections::HashMap;

fn tarjan(
    u: usize,
    parent: Option<usize>,
    time: &mut usize,
    graph: &HashMap<usize, Vec<usize>>,
    disc: &mut Vec<Option<usize>>,
    low: &mut Vec<usize>,
    bridges: &mut Vec<(usize, usize)>,
) {
    *time += 1;
    disc[u] = Some(*time);
    low[u] = *time;

    if let Some(neighbors) = graph.get(&u) {
        for &v in neighbors {
            if disc[v].is_none() {
                tarjan(v, Some(u), time, graph, disc, low, bridges);
                low[u] = low[u].min(low[v]);
                if low[v] > disc[u].unwrap() {
                    bridges.push((u, v));
                }
            } else if Some(v) != parent {
                low[u] = low[u].min(disc[v].unwrap());
            }
        }
    }
}

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

    let n = 7;
    let mut disc = vec![None; n];
    let mut low = vec![0; n];
    let mut bridges = Vec::new();
    let mut time = 0;

    for i in 0..n {
        if disc[i].is_none() {
            tarjan(i, None, &mut time, &graph, &mut disc, &mut low, &mut bridges);
        }
    }

    println!("{:?}", bridges);
}

A [(0, 1), (5, 6)]

B [(5, 6), (1, 3)]

C [(3, 4), (5, 6)]

D [(1, 2), (3, 5)]

💡 Hint

Check edges where removing them disconnects the graph.

Edges (1,3) and (5,6) are bridges because their removal increases connected components. Other edges are part of cycles.

🧠 Conceptual

expert

Why Tarjan's Algorithm Uses DFS for Bridges

Why does Tarjan's algorithm use Depth-First Search (DFS) to find bridges in a graph?

A Because DFS uses less memory than BFS in all cases

B Because BFS cannot detect cycles in graphs

C Because DFS is faster than BFS in all graph problems

D Because DFS explores edges deeply, allowing discovery and low times to detect back edges and bridges efficiently

💡 Hint

Think about how discovery and low times relate to DFS traversal.

DFS allows tracking discovery times and back edges, which are essential to identify bridges by comparing low and discovery times.

Practice

1. What is the main purpose of Tarjan's algorithm when finding bridges in a graph?

easy

A. To detect cycles in a graph

B. To find the shortest path between two nodes

C. To find edges that, if removed, increase the number of connected components

D. To sort nodes in topological order

Solution

1. Step 1: Understand what a bridge is in a graph

   A bridge is an edge that, when removed, increases the number of connected components in the graph.

2. Step 2: Identify Tarjan's algorithm goal

   Tarjan's algorithm finds such edges efficiently by using DFS and tracking discovery and low times.

3. Final Answer:

   To find edges that, if removed, increase the number of connected components -> Option C

4. Quick Check:

   Bridges = edges increasing components [OK]

Hint: Bridges break connectivity when removed [OK]

Common Mistakes:

• Confusing bridges with cycles
• Thinking it finds shortest paths
• Mixing bridges with articulation points

2. Which of the following Rust code snippets correctly declares a vector to store adjacency lists for a graph with 5 nodes?

easy

A. let graph: Vec = vec![vec![0]; 5];

B. let graph: Vec<usize> = vec![0; 5];

C. let graph: Vec = vec![vec![]; 4];

D. let graph: Vec = vec![vec![]; 5];

Solution

1. Step 1: Understand adjacency list representation

   Each node has a vector of neighbors, so graph is a vector of vectors.

2. Step 2: Check vector initialization for 5 nodes

   vec![vec![]; 5] creates 5 empty vectors, one per node.

3. Final Answer:

   let graph: Vec = vec![vec![]; 5]; -> Option D

4. Quick Check:

   Adjacency list for 5 nodes = vec![vec![]; 5] [OK]

Hint: Use vec![vec![]; n] for adjacency lists [OK]

Common Mistakes:

• Using wrong vector type (Vec<usize> instead of Vec)
• Initializing with wrong size
• Filling inner vectors with zeros instead of empty

3. Given the following Rust code snippet implementing part of Tarjan's algorithm, what will be printed as bridges for the graph edges?

let edges = vec![(0,1), (1,2), (2,0), (1,3)];
// Graph: triangle 0-1-2 and a bridge edge 1-3
// After running Tarjan's algorithm, which edges are bridges?
println!("Bridges: {:?}", vec![(1,3)]);

medium

A. Bridges: [(1, 3)]

B. Bridges: [(0, 1), (1, 2), (2, 0)]

C. Bridges: []

D. Bridges: [(0, 3)]

Solution

1. Step 1: Analyze the graph structure

   The edges (0,1), (1,2), (2,0) form a cycle (triangle), so none are bridges.

2. Step 2: Identify the bridge edge

   The edge (1,3) connects node 3 to the triangle and is a bridge because removing it disconnects node 3.

3. Final Answer:

   Bridges: [(1, 3)] -> Option A

4. Quick Check:

   Only edge (1,3) breaks connectivity [OK]

Hint: Edges in cycles are not bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring leaf node connections
• Confusing bridge edges with articulation points

4. Identify the bug in this Rust snippet of Tarjan's algorithm for finding bridges:

fn dfs(u: usize, parent: usize, graph: &Vec, disc: &mut Vec<usize>, low: &mut Vec<usize>, time: &mut usize, bridges: &mut Vec<(usize, usize)>) {
    disc[u] = *time;
    low[u] = *time;
    *time += 1;
    for &v in &graph[u] {
        if v == parent {
            continue;
        }
        if disc[v] == 0 {
            dfs(v, u, graph, disc, low, time, bridges);
            low[u] = low[u].min(low[v]);
            if low[v] > disc[u] {
                bridges.push((u, v));
            }
        } else {
            low[u] = low[u].min(disc[v]);
        }
    }
}

medium

A. disc and low arrays are not initialized with zeros

B. The parent check should be if v != parent instead of v == parent

C. The time variable should be passed by value, not mutable reference

D. The condition low[v] > disc[u] should be low[v] < disc[u]

Solution

1. Step 1: Check initialization of disc and low arrays

   disc and low must be initialized with zeros to detect unvisited nodes (disc[v] == 0).

2. Step 2: Verify other logic correctness

   Parent check and time passing are correct; condition low[v] > disc[u] is correct for bridges.

3. Final Answer:

   disc and low arrays are not initialized with zeros -> Option A

4. Quick Check:

   Uninitialized disc causes wrong visited checks [OK]

Hint: Initialize disc and low with zeros before DFS [OK]

Common Mistakes:

• Not initializing disc and low arrays
• Wrong parent check condition
• Passing time by value instead of mutable reference

5. You have a graph with 6 nodes and edges: (0,1), (1,2), (2,0), (1,3), (3,4), (4,5), (5,3). Using Tarjan's algorithm, which edges are bridges in this graph?

hard

A. [(3, 4), (4, 5), (5, 3)]

B. [(1, 3)]

C. [(0, 1), (1, 2), (2, 0)]

D. [(1, 3), (3, 4)]

Solution

1. Step 1: Analyze graph components

   Nodes 0,1,2 form a cycle (triangle), so edges among them are not bridges. Nodes 3,4,5 form a cycle, so edges among them are not bridges.

2. Step 2: Identify bridge edges

   The edge (1,3) connects the two cycles. Removing (1,3) disconnects the graph, so it is a bridge.

3. Final Answer:

   [(1, 3)] -> Option B

4. Quick Check:

   Only edge connecting components is bridge [OK]

Hint: Bridges connect separate cycles or components [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring connectivity between components
• Confusing bridges with articulation points