Articulation Points in Graph in DSA C++ - 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 C++ code that finds articulation points in a graph?

DSA C++

#include <iostream>
#include <vector>
#include <set>
using namespace std;

void dfs(int u, int parent, vector<vector<int>>& adj, vector<int>& disc, vector<int>& low, vector<bool>& visited, set<int>& articulation_points, int& time) {
    visited[u] = true;
    disc[u] = low[u] = ++time;
    int children = 0;
    for (int v : adj[u]) {
        if (!visited[v]) {
            children++;
            dfs(v, u, adj, disc, low, visited, articulation_points, time);
            low[u] = min(low[u], low[v]);
            if (parent != -1 && low[v] >= disc[u]) {
                articulation_points.insert(u);
            }
        } else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (parent == -1 && children > 1) {
        articulation_points.insert(u);
    }
}

int main() {
    int n = 5;
    vector<vector<int>> adj(n);
    adj[0] = {1, 2};
    adj[1] = {0, 2};
    adj[2] = {0, 1, 3};
    adj[3] = {2, 4};
    adj[4] = {3};

    vector<int> disc(n, -1), low(n, -1);
    vector<bool> visited(n, false);
    set<int> articulation_points;
    int time = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, -1, adj, disc, low, visited, articulation_points, time);
        }
    }

    for (int ap : articulation_points) {
        cout << ap << " ";
    }
    cout << endl;
    return 0;
}

A [3 ]

B [0 2 3 ]

C [1 2 3 ]

D [2 3 ]

💡 Hint

Check which nodes, when removed, increase the number of connected components.

The articulation points are nodes 2 and 3 because removing either disconnects the graph. Node 2 connects the triangle (0,1,2) to node 3, and node 3 connects node 4 to the rest.

🧠 Conceptual

intermediate

Understanding articulation points in a graph

Which of the following statements about articulation points in an undirected graph is true?

A An articulation point is a vertex that has the highest degree in the graph.

B An articulation point is a vertex that is part of every cycle in the graph.

C An articulation point is a vertex that, when removed, increases the number of connected components in the graph.

D An articulation point is a vertex that connects two different graphs.

💡 Hint

Think about what happens to connectivity when a vertex is removed.

An articulation point is a vertex that, if removed along with its edges, increases the number of connected components in the graph. It is critical for connectivity.

🔧 Debug

advanced

Identify the error in articulation points detection code

Consider this snippet from an articulation points detection algorithm. What error will it cause when run?

DSA C++

void dfs(int u, int parent, vector<vector<int>>& adj, vector<int>& disc, vector<int>& low, vector<bool>& visited, set<int>& articulation_points, int& time) {
    visited[u] = true;
    disc[u] = low[u] = ++time;
    int children = 0;
    for (int v : adj[u]) {
        if (!visited[v]) {
            children++;
            dfs(v, u, adj, disc, low, visited, articulation_points, time);
            low[u] = min(low[u], low[v]);
            if (low[v] >= disc[u]) {
                articulation_points.insert(u);
            }
        } else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (parent == -1 && children > 1) {
        articulation_points.insert(u);
    }
}

A It will incorrectly mark the root node as articulation point even if it has only one child.

B It will cause a runtime error due to uninitialized variables.

C It will miss marking some articulation points because it lacks a parent check before insertion.

D It will cause infinite recursion due to missing visited check.

💡 Hint

Check the condition for marking articulation points for the root node.

The condition if (low[v] >= disc[u]) inside the loop marks articulation points, but for the root node, it should only be marked if it has more than one child. Without checking parent != -1, the root node with one child is incorrectly marked.

🚀 Application

advanced

Number of articulation points in a complex graph

Given a graph with 7 vertices and edges: (0-1), (1-2), (2-0), (1-3), (3-4), (4-5), (5-3), (5-6), how many articulation points does it have?

A 3

B 2

C 1

D 0

💡 Hint

Identify vertices whose removal increases connected components.

Vertices 1 and 5 are articulation points. Removing 1 disconnects node 3 and beyond; removing 5 disconnects node 6.

❓ Predict Output

expert

Output of articulation points detection on disconnected graph

What is the output of the following C++ code that finds articulation points in a disconnected graph?

DSA C++

#include <iostream>
#include <vector>
#include <set>
using namespace std;

void dfs(int u, int parent, vector<vector<int>>& adj, vector<int>& disc, vector<int>& low, vector<bool>& visited, set<int>& articulation_points, int& time) {
    visited[u] = true;
    disc[u] = low[u] = ++time;
    int children = 0;
    for (int v : adj[u]) {
        if (!visited[v]) {
            children++;
            dfs(v, u, adj, disc, low, visited, articulation_points, time);
            low[u] = min(low[u], low[v]);
            if (parent != -1 && low[v] >= disc[u]) {
                articulation_points.insert(u);
            }
        } else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (parent == -1 && children > 1) {
        articulation_points.insert(u);
    }
}

int main() {
    int n = 7;
    vector<vector<int>> adj(n);
    adj[0] = {1};
    adj[1] = {0, 2};
    adj[2] = {1};
    adj[3] = {4};
    adj[4] = {3, 5, 6};
    adj[5] = {4};
    adj[6] = {4};

    vector<int> disc(n, -1), low(n, -1);
    vector<bool> visited(n, false);
    set<int> articulation_points;
    int time = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, -1, adj, disc, low, visited, articulation_points, time);
        }
    }

    for (int ap : articulation_points) {
        cout << ap << " ";
    }
    cout << endl;
    return 0;
}

A [1 4 ]

B [0 1 4 ]

C [4 ]

D [1 3 4 ]

💡 Hint

Consider articulation points in each disconnected component separately.

In the first component (0,1,2), node 1 is an articulation point. In the second component (3,4,5,6), node 4 is an articulation point. So output is 1 and 4.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex with the highest degree in the graph

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

C. A vertex connected to all other vertices

D. A vertex that forms a cycle with its neighbors

Solution

1. Step 1: Understand the role of articulation points

   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 which, when removed, increases the number of connected components describes this property correctly; others describe different vertex properties.

3. Final Answer:

   A vertex which, 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 forms cycles
• Assuming articulation point connects to all vertices

2. Which of the following is the correct way to declare a vector of vectors for adjacency list in C++?

easy

A. vector adj;

B. vector adj<int>;

C. vector<int> adj[];

D. vector<vector> adj<int>;

Solution

1. Step 1: Recall correct syntax for 2D vector declaration

   In C++, a vector of vectors is declared as vector name; to represent adjacency lists.

2. Step 2: Check each option

   vector adj; matches correct syntax; A, B and D have syntax errors.

3. Final Answer:

   vector adj; -> Option A

4. Quick Check:

   2D vector syntax = vector [OK]

Hint: Use vector for adjacency lists in C++ [OK]

Common Mistakes:

• Using array syntax instead of vector
• Incorrect template syntax
• Missing angle brackets for nested vectors

3. Consider the following code snippet for finding articulation points in a graph with 4 vertices (0 to 3):

int timer = 0;
vector<int> disc(4, -1), low(4, -1);
vector<bool> visited(4, false), isAP(4, false);
vector adj = {{1, 2}, {0, 2}, {0, 1, 3}, {2}};

void dfs(int u, int parent) {
    visited[u] = true;
    disc[u] = low[u] = timer++;
    int children = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        if (!visited[v]) {
            children++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (parent != -1 && low[v] >= disc[u])
                isAP[u] = true;
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (parent == -1 && children > 1)
        isAP[u] = true;
}

dfs(0, -1);

vector<int> result;
for (int i = 0; i < 4; i++) {
    if (isAP[i]) result.push_back(i);
}
for (int x : result) cout << x << " ";

What will be the output?

medium

A. 2

B. 0 1 2

C. 1 2

D. 0 2

Solution

1. Step 1: Analyze the graph structure and DFS traversal

   The graph edges are: 0-1, 0-2, 1-2, 2-3 (triangle 0-1-2 + pendant 3 on 2). DFS from 0 visits 1 then 2 then 3; when back to 0, 2 already visited so root children=1 (not AP).

2. Step 2: Check articulation point conditions in code

   Root children=1 (<=1, not AP). For non-root u=2 (parent=1), low[3]=3 >= disc[2]=2 so isAP[2]=true. No others. Output is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Root children=1 and vertex 2 disconnects 3 = 2 [OK]

Hint: Root with >1 child and low[v]>=disc[u] mark AP [OK]

Common Mistakes:

• Missing root articulation point condition
• Confusing low and disc arrays
• Ignoring parent check in DFS

4. The following code snippet is intended to find articulation points but has a bug:

void dfs(int u, int parent) {
    visited[u] = true;
    disc[u] = low[u] = timer++;
    int children = 0;
    for (int v : adj[u]) {
        if (!visited[v]) {
            children++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= disc[u])
                isAP[u] = true;
        } else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (parent == -1 && children > 1)
        isAP[u] = true;
}

What is the bug in this code?

medium

A. Not marking visited[u] as true at start

B. Incorrect update of low[u] inside else if block

C. Not incrementing timer before assigning disc[u]

D. Missing check for parent != -1 before marking isAP[u]

Solution

1. Step 1: Understand articulation point condition for non-root nodes

   For non-root nodes, isAP[u] should be set only if parent != -1 and low[v] >= disc[u]. The code misses the parent != -1 check before setting isAP[u].

2. Step 2: Verify other parts of code

   Timer is incremented correctly, visited[u] is set true, low[u] updated properly. So only missing parent check is the bug.

3. Final Answer:

   Missing check for parent != -1 before marking isAP[u] -> Option D

4. Quick Check:

   Parent check needed before marking articulation point [OK]

Hint: Add parent != -1 check before marking articulation point [OK]

Common Mistakes:

• Marking root as articulation point incorrectly
• Confusing order of visited and timer increment
• Ignoring parent in back edge condition

5. Given a connected graph with 5 vertices and edges: 0-1, 1-2, 2-0, 1-3, 3-4, which vertices are articulation points?

hard

A. 1

B. 0 1 3

C. 1 3

D. 3 4

Solution

1. Step 1: Analyze graph connectivity and removal effects

   Vertices 0,1,2 form a triangle (cycle), so none of them alone disconnects graph except vertex 1 which connects to 3 and 4. Removing 1 disconnects 3 and 4. Removing 3 disconnects 4. So 1 and 3 are articulation points.

2. Step 2: Confirm articulation points

   Vertex 1 connects two parts: cycle and chain (3-4). Vertex 3 connects 4 only. Removing 1 or 3 increases components. Vertex 0, 2, 4 are not articulation points.

3. Final Answer:

   1 3 -> Option C

4. Quick Check:

   Removing 1 or 3 disconnects graph = 1 3 [OK]

Hint: Check if removing vertex splits graph into parts [OK]

Common Mistakes:

• Including vertices in cycles as articulation points
• Missing leaf node articulation points
• Confusing articulation points with bridges