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.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex that has no edges connected to it

B. A vertex with the highest degree in the graph

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

D. A vertex connected to all other vertices

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 C

4. Quick Check:

   Articulation point = vertex increasing components when removed [OK]

Hint: Articulation point splits graph if removed [OK]

Common Mistakes:

• Confusing articulation point with highest degree vertex
• Thinking articulation point is always connected to all vertices
• Assuming isolated vertices are articulation points

2. Which of the following is the correct way to declare a graph adjacency list in C++ for articulation point detection?

easy

A. int graph[100][100];

B. vector<int> graph[100];

C. int* graph = malloc(sizeof(int) * 100);

D. int graph[100];

Solution

1. Step 1: Understand adjacency list representation

   An adjacency list stores neighbors for each vertex, best done with an array of vectors in C++ or array of lists in C.

2. Step 2: Analyze options

   vector<int> graph[100];: vector<int> graph[100]; is correct for adjacency list in C++ (common in DSA). int graph[100][100]; is 2D array (adjacency matrix). int* graph = malloc(sizeof(int) * 100); is incorrect memory allocation. int graph[100]; is single array, insufficient for lists.

3. Final Answer:

   vector<int> graph[100]; -> Option B

4. Quick Check:

   Adjacency list = array of vectors [OK]

Hint: Use array of vectors for adjacency list in C++ [OK]

Common Mistakes:

• Using 2D arrays for adjacency list instead of adjacency matrix
• Incorrect memory allocation for adjacency list
• Confusing adjacency list with adjacency matrix

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

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

What will be the value of articulation[1] after running dfs(0, -1) on the graph edges: 0-1, 1-2, 1-3?

medium

A. true

B. false

C. undefined

D. depends on order

Solution

1. Step 1: Analyze graph structure and DFS

   Graph edges: 0-1, 1-2, 1-3. Vertex 1 connects 0 to 2 and 3. Removing 1 disconnects graph.

2. Step 2: Apply articulation point logic

   Since 1 is not root (parent != -1) and low[v] >= disc[u] condition holds for children 2 and 3, articulation[1] is set true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Vertex 1 disconnects graph = articulation true [OK]

Hint: Check if removing vertex splits graph [OK]

Common Mistakes:

• Assuming root node logic applies to vertex 1
• Ignoring low and disc comparison
• Confusing parent and child roles in DFS

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

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

medium

A. The visited array is not updated

B. The variable children is not incremented

C. The parent parameter is not passed correctly

D. The condition low[v] > disc[u] should be low[v] >= disc[u]

Solution

1. Step 1: Review articulation point condition

   The condition for articulation point when parent != -1 is low[v] >= disc[u], not strictly greater.

2. Step 2: Identify impact of wrong condition

   Using low[v] > disc[u] misses cases where low[v] == disc[u], causing missed articulation points.

3. Final Answer:

   The condition low[v] > disc[u] should be low[v] >= disc[u] -> Option D

4. Quick Check:

   Use >= to detect articulation points correctly [OK]

Hint: Use >= not > for articulation condition [OK]

Common Mistakes:

• Using > instead of >= in low and disc comparison
• Forgetting to increment children count
• Not marking visited vertices

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

hard

A. [1,3]

B. [1,4]

C. [0,2,4]

D. [3,5]

Solution

1. Step 1: Analyze graph structure

   Triangles: 0-1-2 and 3-4-5. Vertex 1 connects 0-1-2 triangle to 3-4-5 cluster via 1-3. Vertex 3 connects 1 to the 3-4-5 triangle.

2. Step 2: Identify articulation points

   Removing 1 disconnects {0,2} from {3,4,5}. Removing 3 disconnects {0,1,2} from {4,5} (4-5 still connected). So articulation points are 1 and 3.

3. Final Answer:

   [1,3] -> Option A

4. Quick Check:

   Vertices splitting graph = 1 and 3 [OK]

Hint: Check vertices connecting separate cycles [OK]

Common Mistakes:

• Including vertices inside cycles as articulation points
• Missing articulation points connecting clusters
• Confusing articulation points with bridges