Bridges in Graph Tarjan's Algorithm in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the discovery time for the current node in Tarjan's algorithm.

DSA Rust

disc[u] = [1];
low[u] = time;
time += 1;

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

Au

B0

Ctime

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting discovery time to 0 or node index instead of current time.

Forgetting to assign low[u] the same initial value.

The discovery time for node u is set to the current time counter before incrementing it.

2fill in blank

medium

Complete the code to update the low value of the current node after visiting a neighbor in Tarjan's algorithm.

DSA Rust

low[u] = [1](low[u], low[v]);

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

Amax

Bmin

Cabs

Dsum

Attempts:

3 left

💡 Hint

Common Mistakes

Using max instead of min causes incorrect bridge detection.

Using sum or abs is not meaningful here.

The low value is updated to the minimum of its current low and the neighbor's low value.

3fill in blank

hard

Fix the error in the condition that detects a bridge edge in Tarjan's algorithm.

DSA Rust

if low[v] [1] disc[u] {
    bridges.push((u, v));
}

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

A>

B<

C!=

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' or '==' causes incorrect bridge detection.

Using '!=' is not a valid condition for bridges.

An edge (u, v) is a bridge if low[v] > disc[u], meaning v cannot reach an ancestor of u.

4fill in blank

hard

Fill both blanks to correctly skip the parent node and update low value for back edges.

DSA Rust

for &v in graph[u].iter() {
    if v == [1] {
        continue;
    }
    if disc[v] != -1 {
        low[u] = [2](low[u], disc[v]);
    }
}

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

Aparent

Btime

Cmin

Dmax

Attempts:

3 left

💡 Hint

Common Mistakes

Not skipping the parent node causes incorrect low values.

Using max instead of min leads to wrong bridge detection.

We skip the parent node to avoid trivial cycles, and update low[u] with the minimum of low[u] and disc[v] for back edges.

5fill in blank

hard

Fill all three blanks to complete the recursive DFS call and update low value after recursion.

DSA Rust

for &v in graph[u].iter() {
    if v != [1] {
        if disc[v] == -1 {
            dfs(v, u, disc, low, graph, bridges, [2]);
            low[u] = [3](low[u], low[v]);
        }
    }
}

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

Aparent

Btime

Cmin

Dmax

Attempts:

3 left

💡 Hint

Common Mistakes

Passing wrong variable instead of time causes incorrect discovery times.

Using max instead of min breaks bridge detection logic.

We recurse on neighbors not equal to parent, pass the current time counter, and update low[u] with the minimum of low[u] and low[v].

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