Articulation Points in Graph in DSA C++

Mental Model

An articulation point is a node in a graph that, if removed, breaks the graph into more pieces. It shows where the graph is fragile.

Analogy: Imagine a city connected by roads. An articulation point is like a critical bridge or intersection; if it closes, parts of the city become unreachable from each other.

Graph:
  1
 / \
2 - 3
|
4

Articulation points: 2 and 3 because removing them splits the graph.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 1-3, 2-3, 2-4

Goal: Find nodes that, if removed, increase the number of disconnected parts in the graph.

Step 1: Start DFS from node 1, set discovery time and low value to 1

Visited: 1 (disc=1, low=1)
Stack: [1]

Why: We begin exploring the graph from node 1 to find articulation points.

Step 2: Visit node 2 from 1, set disc=2, low=2

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2)
Stack: [1,2]

Why: We explore neighbors to find back edges and update low values.

Step 3: Visit node 3 from 2, set disc=3, low=3

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2), 3 (disc=3, low=3)
Stack: [1,2,3]

Why: Continue DFS to explore deeper nodes.

Step 4: Node 3 has neighbor 1 already visited, update low[3] = min(low[3], disc[1]) = 1

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2), 3 (disc=3, low=1)
Stack: [1,2,3]

Why: Back edge from 3 to 1 lowers low value, showing a cycle.

Step 5: Back to node 2, update low[2] = min(low[2], low[3]) = 1

Visited: 1 (disc=1, low=1), 2 (disc=2, low=1), 3 (disc=3, low=1)
Stack: [1,2,3]

Why: Low value propagates up to parent to detect articulation points.

Step 6: Visit node 4 from 2, set disc=4, low=4

Visited: 1 (disc=1, low=1), 2 (disc=2, low=1), 3 (disc=3, low=1), 4 (disc=4, low=4)
Stack: [1,2,3,4]

Why: Explore new branch to check if node 2 is articulation point.

Step 7: Node 4 has no unvisited neighbors, backtrack and update low[2] = min(low[2], low[4]) = 1

Visited: 1 (disc=1, low=1), 2 (disc=2, low=1), 3 (disc=3, low=1), 4 (disc=4, low=4)
Stack: [1,2,3,4]

Why: No back edges from 4, low value stays 4.

Step 8: Check articulation point condition at node 2: low[4] >= disc[2] (4 >= 2) true, mark 2 as articulation point

Articulation points: {2}

Why: Removing node 2 disconnects node 4 from the graph.

Result:

Articulation points: 2
Graph after removing 2 splits into parts: {1,3} and {4}

Annotated Code

DSA C++

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

class Graph {
public:
    int V;
    vector<vector<int>> adj;
    Graph(int V) : V(V), adj(V) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void APUtil(int u, vector<bool>& visited, vector<int>& disc, vector<int>& low, vector<int>& parent, set<int>& ap, int& time) {
        visited[u] = true;
        disc[u] = low[u] = ++time; // discovery time and low value

        int children = 0;
        for (int v : adj[u]) {
            if (!visited[v]) {
                children++;
                parent[v] = u;
                APUtil(v, visited, disc, low, parent, ap, time);

                low[u] = min(low[u], low[v]); // update low value

                // articulation point check
                if (parent[u] == -1 && children > 1) {
                    ap.insert(u); // root with two or more children
                }
                if (parent[u] != -1 && low[v] >= disc[u]) {
                    ap.insert(u); // non-root condition
                }
            } else if (v != parent[u]) {
                low[u] = min(low[u], disc[v]); // back edge
            }
        }
    }

    set<int> findArticulationPoints() {
        vector<bool> visited(V, false);
        vector<int> disc(V, -1);
        vector<int> low(V, -1);
        vector<int> parent(V, -1);
        set<int> ap;
        int time = 0;

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                APUtil(i, visited, disc, low, parent, ap, time);
            }
        }
        return ap;
    }
};

int main() {
    Graph g(5); // nodes 0 to 4
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(2, 4);

    set<int> articulationPoints = g.findArticulationPoints();
    cout << "Articulation points:";
    for (int ap : articulationPoints) {
        cout << " " << ap;
    }
    cout << "\n";
    return 0;
}

disc[u] = low[u] = ++time; // discovery time and low value

Assign discovery and low time when visiting node u

for (int v : adj[u]) { if (!visited[v]) { ... } else if (v != parent[u]) { low[u] = min(low[u], disc[v]); } }

Traverse neighbors; update low[u] for back edges

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

Root node with multiple children is articulation point

if (parent[u] != -1 && low[v] >= disc[u]) { ap.insert(u); }

Non-root node is articulation point if no back edge from child v to ancestors

Output

Articulation points: 2

Complexity Analysis

Time: O(V + E) because we do a DFS traversal visiting each vertex and edge once

Space: O(V) for arrays to store visited, discovery, low, parent, and recursion stack

vs Alternative: Naive approach checks connectivity after removing each node, costing O(V*(V+E)), much slower than DFS-based O(V+E)

Edge Cases

Graph with no edges

No articulation points because no node removal disconnects graph

DSA C++

if (!visited[i]) { APUtil(i, visited, disc, low, parent, ap, time); }

Graph with single node

No articulation points because removing the only node leaves empty graph

DSA C++

if (!visited[i]) { APUtil(i, visited, disc, low, parent, ap, time); }

Graph with multiple disconnected components

Algorithm runs DFS on each component separately to find articulation points in all parts

DSA C++

for (int i = 0; i < V; i++) { if (!visited[i]) { APUtil(...); } }

When to Use This Pattern

When a problem asks for nodes whose removal increases disconnected parts, use articulation points detection with DFS low and discovery times.

Common Mistakes

Mistake: Not updating low[u] for back edges to ancestors, missing articulation points
Fix: Update low[u] = min(low[u], disc[v]) when visiting an already visited neighbor v not parent

Mistake: Marking root node as articulation point without checking if it has multiple children
Fix: Only mark root as articulation point if it has two or more children in DFS tree

Summary

Find nodes that disconnect the graph if removed.

Use when you need to identify critical points in network connectivity.

Track discovery and low times in DFS to detect articulation points.

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