Articulation Points in Graph in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of articulation points detection on a simple graph

What is the output of the following Rust code that finds articulation points in a graph?

DSA Rust

use std::collections::HashMap;

fn articulation_points(
    graph: &HashMap<usize, Vec<usize>>,
    u: usize,
    visited: &mut Vec<bool>,
    disc: &mut Vec<usize>,
    low: &mut Vec<usize>,
    parent: &mut Vec<Option<usize>>,
    ap: &mut Vec<bool>,
    time: &mut usize,
) {
    visited[u] = true;
    *time += 1;
    disc[u] = *time;
    low[u] = *time;
    let mut children = 0;

    for &v in &graph[&u] {
        if !visited[v] {
            children += 1;
            parent[v] = Some(u);
            articulation_points(graph, v, visited, disc, low, parent, ap, time);
            low[u] = low[u].min(low[v]);

            if parent[u].is_none() && children > 1 {
                ap[u] = true;
            }

            if parent[u].is_some() && low[v] >= disc[u] {
                ap[u] = true;
            }
        } else if Some(v) != parent[u] {
            low[u] = low[u].min(disc[v]);
        }
    }
}

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, 5]);
    graph.insert(3, vec![2, 4]);
    graph.insert(4, vec![3]);
    graph.insert(5, vec![2, 6, 7]);
    graph.insert(6, vec![5, 7]);
    graph.insert(7, vec![5, 6]);

    let n = 8;
    let mut visited = vec![false; n];
    let mut disc = vec![0; n];
    let mut low = vec![0; n];
    let mut parent = vec![None; n];
    let mut ap = vec![false; n];
    let mut time = 0;

    for i in 0..n {
        if !visited[i] {
            articulation_points(&graph, i, &mut visited, &mut disc, &mut low, &mut parent, &mut ap, &mut time);
        }
    }

    let result: Vec<usize> = ap.iter().enumerate().filter_map(|(i, &x)| if x { Some(i) } else { None }).collect();
    println!("{:?}", result);
}

A [2, 4, 7]

B [2, 3, 5]

C [1, 3, 6]

D [0, 2, 5]

💡 Hint

Focus on nodes whose removal increases the number of connected components.

Nodes 2, 3, and 5 are articulation points because removing any of them disconnects parts of the graph.

🧠 Conceptual

intermediate

Understanding articulation points in a graph

Which of the following best describes an articulation point in a connected graph?

A A vertex that, when removed, increases the number of connected components.

B A vertex with the highest degree in the graph.

C A vertex that is connected to all other vertices.

D A vertex that has no edges connected to it.

💡 Hint

Think about the effect of removing a vertex on graph connectivity.

An articulation point is a vertex whose removal disconnects the graph into more components.

🔧 Debug

advanced

Identify the error in articulation points detection code

What error will the following Rust code produce when run?

DSA Rust

use std::collections::HashMap;

fn articulation_points(
    graph: &HashMap<usize, Vec<usize>>,
    u: usize,
    visited: &mut Vec<bool>,
    disc: &mut Vec<usize>,
    low: &mut Vec<usize>,
    parent: &mut Vec<Option<usize>>,
    ap: &mut Vec<bool>,
    time: &mut usize,
) {
    visited[u] = true;
    *time += 1;
    disc[u] = *time;
    low[u] = *time;
    let mut children = 0;

    for &v in &graph[&u] {
        if !visited[v] {
            children += 1;
            parent[v] = Some(u);
            articulation_points(graph, v, visited, disc, low, parent, ap, time);
            low[u] = low[u].min(low[v]);

            if parent[u].is_none() && children > 1 {
                ap[u] = true;
            }

            if parent[u].is_some() && low[v] >= disc[u] {
                ap[u] = true;
            }
        } else if Some(v) != parent[u] {
            low[u] = low[u].min(disc[v]);
        }
    }
}

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

    let n = 3;
    let mut visited = vec![false; n];
    let mut disc = vec![0; n];
    let mut low = vec![0; n];
    let mut parent = vec![None; n];
    let mut ap = vec![false; n];
    let mut time = 0;

    for i in 0..n {
        if !visited[i] {
            articulation_points(&graph, i, &mut visited, &mut disc, &mut low, &mut parent, &mut ap, &mut time);
        }
    }

    let result: Vec<usize> = ap.iter().enumerate().filter_map(|(i, &x)| if x { Some(i) } else { None }).collect();
    println!("{:?}", result);
}

A Panic at runtime due to missing keys in the graph HashMap.

B Compilation error due to mutable borrow conflict.

C No output because the graph is empty.

D Correct output with articulation points printed.

💡 Hint

Check if all nodes have entries in the graph map.

Node 2's adjacency list is missing some neighbors causing a panic when accessed.

📝 Syntax

advanced

Identify the syntax error in articulation points function

Which option contains a syntax error in the Rust articulation points function?

DSA Rust

fn articulation_points(
    graph: &HashMap<usize, Vec<usize>>,
    u: usize,
    visited: &mut Vec<bool>,
    disc: &mut Vec<usize>,
    low: &mut Vec<usize>,
    parent: &mut Vec<Option<usize>>,
    ap: &mut Vec<bool>,
    time: &mut usize,
) {
    visited[u] = true
    *time += 1;
    disc[u] = *time;
    low[u] = *time;
    // rest of code omitted
}

A Using &mut Vec<bool> instead of &Vec<bool>

B Incorrect type for time parameter

C Missing return type in function signature

D Missing semicolon after visited[u] = true

💡 Hint

Look carefully at line endings.

Rust requires semicolons after statements; missing one causes a syntax error.

🚀 Application

expert

Number of articulation points in a complex graph

Given a graph with 10 nodes and edges: 0-1, 1-2, 2-3, 3-4, 2-5, 5-6, 6-7, 7-5, 6-8, 8-9 How many articulation points does this graph have?

A 3

B 2

C 4

D 5

💡 Hint

Identify nodes whose removal disconnects parts of the graph.

Nodes 1, 2, 3, and 6 are articulation points in this graph.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex with the highest degree in the graph

B. A vertex that, when removed, increases the number of connected components

C. A vertex that has no edges connected to it

D. A vertex that forms a cycle with its neighbors

Solution

1. Step 1: Understand articulation point definition

   An articulation point is a vertex that, if removed, breaks the graph into more pieces (connected components).

2. Step 2: Compare options with definition

   Only A vertex that, when removed, increases the number of connected components matches this definition exactly.

3. Final Answer:

   A vertex that, when removed, increases the number of connected components -> Option B

4. Quick Check:

   Articulation point = vertex increasing components when removed [OK]

Hint: Articulation point breaks graph connectivity when removed [OK]

Common Mistakes:

• Confusing articulation point with highest degree vertex
• Thinking articulation point is a vertex with no edges
• Mixing articulation point with cycle forming vertex

2. Which Rust data structure is best suited to store the graph for finding articulation points?

easy

A. Vec (adjacency list)

B. HashMap

C. Vec<usize> (simple list)

D. String

Solution

1. Step 1: Identify graph representation for articulation points

   Graphs are commonly stored as adjacency lists for efficient traversal and edge lookup.

2. Step 2: Match Rust data structures

   Vec represents adjacency lists well, storing neighbors for each vertex.

3. Final Answer:

   Vec (adjacency list) -> Option A

4. Quick Check:

   Adjacency list = Vec in Rust [OK]

Hint: Use adjacency list (Vec of Vec) for graph edges [OK]

Common Mistakes:

• Using HashMap which is unrelated
• Using simple Vec<usize> which can't store edges
• Using String which is not a graph structure

3. What is the output of the following Rust code snippet that finds articulation points in a graph?

let graph = vec![
    vec![1, 2],
    vec![0, 2],
    vec![0, 1, 3],
    vec![2, 4],
    vec![3]
];
// Articulation points found: [2, 3]
println!("{:?}", find_articulation_points(&graph));

medium

A. [1, 4]

B. [0, 1]

C. [2, 3]

D. []

Solution

1. Step 1: Analyze graph structure

   Vertices 2 and 3 connect parts of the graph such that removing them increases components.

2. Step 2: Identify articulation points

   Removing vertex 2 disconnects vertex 3 and 4; removing vertex 3 disconnects vertex 4.

3. Final Answer:

   [2, 3] -> Option C

4. Quick Check:

   Vertices 2 and 3 are articulation points [OK]

Hint: Check vertices whose removal splits graph [OK]

Common Mistakes:

• Choosing vertices with no articulation role
• Ignoring connectivity after removal
• Assuming leaf nodes are articulation points

4. Identify the bug in this Rust code snippet for finding articulation points:

fn dfs(u: usize, graph: &Vec, visited: &mut Vec<bool>, disc: &mut Vec<usize>, low: &mut Vec<usize>, parent: &mut Vec, time: &mut usize) {
    visited[u] = true;
    disc[u] = *time;
    low[u] = *time;
    *time += 1;

    for &v in &graph[u] {
        if !visited[v] {
            parent[v] = Some(u);
            dfs(v, graph, visited, disc, low, parent, time);
            low[u] = low[u].min(low[v]);
        } else if v != parent[u].unwrap() {
            low[u] = low[u].min(disc[v]);
        }
    }
}

medium

A. Not updating low[v] after recursion

B. Not marking visited[u] as true

C. Not incrementing time variable

D. Using unwrap() on parent[u] without checking if it is Some

Solution

1. Step 1: Check unwrap usage on parent[u]

   parent[u] may be None for root node, unwrap() causes panic if None.

2. Step 2: Identify safe handling

   Code should check if parent[u] is Some before unwrap or handle root separately.

3. Final Answer:

   Using unwrap() on parent[u] without checking if it is Some -> Option D

4. Quick Check:

   Unsafe unwrap on Option causes runtime panic [OK]

Hint: Check Option unwrap safety for root node [OK]

Common Mistakes:

• Ignoring root node parent None case
• Assuming unwrap() is always safe
• Missing visited marking (actually present here)

5. Given a graph with multiple disconnected components, how should the articulation points algorithm be adapted in Rust to find all articulation points?

hard

A. Run DFS from every unvisited vertex to cover all components

B. Run DFS only from vertex 0 assuming graph is connected

C. Run BFS instead of DFS for articulation points

D. Ignore disconnected components as they have no articulation points

Solution

1. Step 1: Understand disconnected graph scenario

   Articulation points can exist in any component, so all must be checked.

2. Step 2: Adapt algorithm to run DFS on all components

   Run DFS from every unvisited vertex to cover all disconnected parts.

3. Final Answer:

   Run DFS from every unvisited vertex to cover all components -> Option A

4. Quick Check:

   Multiple DFS runs cover all components [OK]

Hint: Run DFS on all unvisited nodes for full coverage [OK]

Common Mistakes:

• Assuming graph is always connected
• Using BFS which doesn't track articulation points easily
• Ignoring disconnected components