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
     |
     5

Node 3 is an articulation point because removing it splits the graph.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 1-3, 2-3, 3-4, 3-5; find articulation points

Goal: Identify nodes that, when removed, increase the number of disconnected parts in the graph

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

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

Why: We begin exploring the graph and mark the first node's discovery time

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

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

Why: Explore unvisited neighbor 2

Step 3: Visit node 3 from 2, assign disc=3, low=3; find back edge to 1, update low[3]=1

Visited: 1(1,1), 2(2,2), 3(3,1)
Stack: [1,2,3]
Articulation Points: []

Why: Back edge 3-1 allows subtree to reach ancestor of 2, low[3] updated to disc[1]

Step 4: Visit node 4 from 3, assign disc=4, low=4

Visited: ... 4(4,4)
Stack: [1,2,3,4]
Articulation Points: []

Why: Node 4 is a leaf node

Step 5: Backtrack from 4 to 3, low[3]=min(1,4)=1; low[4]=4 >= disc[3]=3 && parent != -1, mark 3 as AP

Visited: ... 3(3,1)
Stack: [1,2,3]
Articulation Points: [3]

Why: No back edge from 4's subtree to ancestors of 3, so 3 is articulation point

Step 6: Visit node 5 from 3, assign disc=5, low=5

Visited: ... 5(5,5)
Stack: [1,2,3,5]
Articulation Points: [3]

Why: Node 5 is another leaf

Step 7: Backtrack from 5 to 3, low[3]=min(1,5)=1; low[5]=5 >= disc[3]=3, mark 3 as AP

Visited: ... 3(3,1)
Stack: [1,2,3]
Articulation Points: [3]

Why: No back edge from 5's subtree to ancestors of 3

Step 8: Backtrack from 3 to 2, low[2]=min(2,1)=1; low[3]=1 < disc[2]=2, do not mark 2

Visited: 1(1,1), 2(2,1), 3(3,1)
Stack: [1,2]
Articulation Points: [3]

Why: Subtree rooted at 3 can reach ancestors of 2 via back edge to 1

Step 9: Backtrack from 2 to 1, low[1]=min(1,1)=1; low[2]=1 >= disc[1]=1 but parent=-1 (root), do not mark; neighbor 3 is back edge, no update; root has 1 child, not AP

All visited
Articulation Points: [3]

Why: Root is not an articulation point as it has only one child in DFS tree

Result:

Articulation Points: 3
Removing node 3 disconnects 4 and 5 from the rest

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 100

int time_counter = 0;

void dfs(int u, int parent, int disc[], int low[], bool visited[], int graph[MAX][MAX], int n, bool articulation_points[]) {
    visited[u] = true;
    disc[u] = low[u] = ++time_counter;
    int children = 0;

    for (int v = 0; v < n; v++) {
        if (graph[u][v]) {
            if (!visited[v]) {
                children++;
                dfs(v, u, disc, low, visited, graph, n, articulation_points);
                if (low[v] >= disc[u] && parent != -1) {
                    articulation_points[u] = true;
                }
                low[u] = (low[v] < low[u]) ? low[v] : low[u];
            } else if (v != parent) {
                low[u] = (disc[v] < low[u]) ? disc[v] : low[u];
            }
        }
    }

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

int main() {
    int n = 5; // nodes 0 to 4 (1-5 1-based)
    int graph[MAX][MAX] = {0};

    // Edges: 1-2,1-3,2-3,3-4,3-5 -> 0-1,0-2,1-2,2-3,2-4
    graph[0][1] = graph[1][0] = 1;
    graph[0][2] = graph[2][0] = 1;
    graph[1][2] = graph[2][1] = 1;
    graph[2][3] = graph[3][2] = 1;
    graph[2][4] = graph[4][2] = 1;

    bool visited[MAX] = {false};
    int disc[MAX] = {0}, low[MAX] = {0};
    bool articulation_points[MAX] = {false};

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

    printf("Articulation Points: ");
    bool found = false;
    for (int i = 0; i < n; i++) {
        if (articulation_points[i]) {
            printf("%d ", i + 1);
            found = true;
        }
    }
    if (!found) printf("None");
    printf("\n");

    return 0;
}

visited[u] = true; disc[u] = low[u] = ++time_counter;

Mark node u as visited and set discovery and low times

for (int v = 0; v < n; v++) { if (graph[u][v]) { ... } }

Explore all adjacent nodes v of u

if (!visited[v]) { children++; dfs(v, u, ...); }

Recur to unvisited child v, increment child count for root check

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

Mark u as AP if subtree rooted at v has no back edge to ancestor of u (non-root)

low[u] = (low[v] < low[u]) ? low[v] : low[u];

Propagate the smallest low value from child subtree

else if (v != parent) { low[u] = (disc[v] < low[u]) ? disc[v] : low[u]; }

Back edge to ancestor v updates low[u] to disc[v]

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

Root with >=2 children in DFS tree is an articulation point

Output

Articulation Points: 3 

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during DFS

Space: O(V) for arrays (disc, low, visited, AP) and recursion stack

vs Alternative: Naive: O(V*(V+E)) by removing each vertex and running DFS/BFS for connectivity check

Edge Cases

Graph with no edges (isolated nodes)

No articulation points; each node is a trivial component

DSA C

Root check requires children > 1; leaves have no children

Single node

No AP; empty graph after removal

DSA C

parent==-1 && children>1 false (children=0)

Multiple components

DFS called on each; APs found independently per component

DSA C

Loop over all nodes: for (int i=0; i<n; i++) if(!visited[i]) dfs(i,-1,...)

Complete graph (clique)

No APs; remains connected after removing any single node

DSA C

Low values propagate via back edges, low[v] < disc[u] always

When to Use This Pattern

When a problem asks for nodes whose removal disconnects the graph or increases components, use articulation points detection with DFS, discovery/low values.

Common Mistakes

Mistake: Forgetting special case for root node
Fix: Count children in DFS tree; mark root AP only if children > 1

Mistake: Incorrect low/disc update order or missing back edge handling
Fix: Update low[u] after recursion on children and for back edges separately

Mistake: Not marking AP only once (using bool array)
Fix: Use boolean array; set to true if condition met (idempotent)

Mistake: Assuming undirected graph is handled; missing adj matrix symmetry
Fix: Set graph[u][v] = graph[v][u] = 1 for undirected

Summary

Articulation points (cut vertices) are found using DFS with discovery time, low values, and child counts.

Key insight: low[v] >= disc[u] means no back edge from v's subtree to u's ancestors.

Root special case: >1 child. Time O(V+E), vital for network reliability analysis.