Articulation Points in Graph in DSA C++ - Build from Scratch

Articulation Points in Graph

📖 Scenario: Imagine a city's road network represented as a graph. Each intersection is a node, and roads are edges connecting them. Some intersections are critical: if they close, parts of the city become unreachable. These are called articulation points.

🎯 Goal: You will build a program to find all articulation points in a given undirected graph. This helps identify critical intersections in the city.

📋 What You'll Learn

Create an adjacency list for the graph with 5 nodes and specified edges

Add variables to track discovery times, low values, and articulation points

Implement a Depth-First Search (DFS) function to find articulation points

Print all articulation points found in the graph

💡 Why This Matters

🌍 Real World

Finding articulation points helps city planners identify critical intersections that, if blocked, can disrupt traffic flow.

💼 Career

Understanding articulation points is important for network reliability analysis, infrastructure planning, and cybersecurity.

1

Create the graph adjacency list

Create an adjacency list called graph as a vector of vectors of integers with 5 nodes (0 to 4). Add edges to represent these connections: 0-1, 0-2, 1-2, 1-3, and 3-4.

DSA C++

# Create the graph adjacency list with 5 nodes and add edges
# Your code here

Hint

Use vector> graph(5); to create the adjacency list. Add edges by pushing back neighbors for both nodes since the graph is undirected.

2

Add tracking variables for DFS

Add integer variables time initialized to 0, and vectors disc, low, and visited each of size 5. Initialize disc and low with -1, and visited with false. Also add a vector articulation_points of booleans of size 5 initialized to false.

DSA C++

#include 
#include 

using namespace std;

int main() {
    vector> graph(5);
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[0].push_back(2);
    graph[2].push_back(0);
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[1].push_back(3);
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[4].push_back(3);

    // Add variables time, disc, low, visited, and articulation_points below
    // Your code here

    return 0;
}

Hint

Use vector to create disc, low, and visited with size 5. Initialize disc and low with -1, and visited and articulation_points with false.

3

Implement DFS to find articulation points

Write a recursive function dfs with parameters int u, int parent, and references to graph, visited, disc, low, articulation_points, and time. Inside dfs, mark u visited, set disc[u] and low[u] to time and increment time. For each neighbor v of u, if not visited, recursively call dfs(v, u, ...), update low[u], and check articulation point conditions. If visited and v != parent, update low[u]. In main, call dfs for each unvisited node starting with parent -1.

DSA C++

#include 
#include 

using namespace std;

// Define dfs function here

int main() {
    vector> graph(5);
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[0].push_back(2);
    graph[2].push_back(0);
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[1].push_back(3);
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[4].push_back(3);

    int time = 0;
    vector disc(5, -1);
    vector low(5, -1);
    vector visited(5, false);
    vector articulation_points(5, false);

    // Call dfs for each unvisited node
    // Your code here

    return 0;
}

Hint

Use the standard DFS approach for articulation points. Track discovery and low times. Mark articulation points when conditions meet. Remember to handle root node separately.

4

Print all articulation points

Add a loop in main to print all node indices i where articulation_points[i] is true. Print each index on its own line.

DSA C++

#include 
#include 

using namespace std;

void dfs(int u, int parent, vector>& graph, vector& visited, vector& disc, vector& low, vector& articulation_points, int& time) {
    visited[u] = true;
    disc[u] = low[u] = time++;
    int children = 0;

    for (int v : graph[u]) {
        if (!visited[v]) {
            children++;
            dfs(v, u, graph, visited, disc, low, articulation_points, time);
            low[u] = min(low[u], low[v]);

            if (parent != -1 && low[v] >= disc[u]) {
                articulation_points[u] = true;
            }
        } else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }

    if (parent == -1 && children > 1) {
        articulation_points[u] = true;
    }
}

int main() {
    vector> graph(5);
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[0].push_back(2);
    graph[2].push_back(0);
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[1].push_back(3);
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[4].push_back(3);

    int time = 0;
    vector disc(5, -1);
    vector low(5, -1);
    vector visited(5, false);
    vector articulation_points(5, false);

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

    // Print articulation points below
    // Your code here

    return 0;
}

Hint

Loop through articulation_points and print the index i if articulation_points[i] is true. Each index should be printed on its own line.

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