Articulation Points in Graph in DSA C - Build from Scratch

Articulation Points in Graph

📖 Scenario: You are working as a network engineer. You want to find critical computers (nodes) in a network that, if removed, would break the network into disconnected parts. These critical nodes are called articulation points.We will represent the network as a graph using adjacency lists.

🎯 Goal: Build a program in C to find all articulation points in an undirected graph using DFS and low-link values.

📋 What You'll Learn

Create an adjacency list representation of the graph with 5 nodes and given edges

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

Implement DFS to find articulation points using Tarjan's algorithm

Print all articulation points found in the graph

💡 Why This Matters

🌍 Real World

Finding articulation points helps identify critical nodes in computer networks, social networks, or transportation systems that can cause disconnection if removed.

💼 Career

Network engineers, system architects, and software developers use articulation point detection to improve network reliability and fault tolerance.

1

Create the graph adjacency list

Create an integer V with value 5 for number of vertices. Create an adjacency list array called adj of size V where each element is a pointer to an integer array. Initialize the adjacency list with these edges: 0-1, 0-2, 1-2, 1-3, 3-4.

DSA C

# Define number of vertices and adjacency list
// Your code here

Hint

Use an array of pointers for adjacency list. Use a helper function add_edge to add edges both ways.

2

Add arrays for DFS tracking

Add integer arrays disc, low, and parent of size V. Also add a boolean array ap of size V to mark articulation points. Initialize all disc and low values to -1, all parent values to -1, and all ap values to 0.

DSA C

#include 
#include 

int V = 5;
int* adj[5];
int adj_size[5] = {0};

void add_edge(int u, int v) {
    adj[u][adj_size[u]++] = v;
    adj[v][adj_size[v]++] = u;
}

int main() {
    for (int i = 0; i < V; i++) {
        adj[i] = (int*)malloc(5 * sizeof(int));
    }

    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 2);
    add_edge(1, 3);
    add_edge(3, 4);

    // Add arrays disc, low, parent, ap and initialize
    // Your code here

    return 0;
}

Hint

Use arrays of size V to track discovery time, low values, parents, and articulation points. Initialize them properly.

3

Implement DFS to find articulation points

Write a recursive function APUtil with parameters int u, int* time. Inside, set disc[u] and low[u] to ++(*time). Use a variable children to count DFS tree children. For each adjacent vertex v of u, if disc[v] is -1, set parent[v] = u, recursively call APUtil(v, time), update low[u] with minimum of low[u] and low[v]. Mark ap[u] = 1 if u is root with more than one child or if low[v] >= disc[u] for non-root. If disc[v] is not -1 and v != parent[u], update low[u] with minimum of low[u] and disc[v]. Call APUtil for all vertices with disc[i] == -1 in main.

DSA C

#include 
#include 

int V = 5;
int* adj[5];
int adj_size[5] = {0};

void add_edge(int u, int v) {
    adj[u][adj_size[u]++] = v;
    adj[v][adj_size[v]++] = u;
}

int disc[5];
int low[5];
int parent[5];
int ap[5];

// Implement APUtil function here
// Your code here

int main() {
    for (int i = 0; i < V; i++) {
        adj[i] = (int*)malloc(5 * sizeof(int));
    }

    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 2);
    add_edge(1, 3);
    add_edge(3, 4);

    for (int i = 0; i < V; i++) {
        disc[i] = -1;
        low[i] = -1;
        parent[i] = -1;
        ap[i] = 0;
    }

    int time = 0;
    for (int i = 0; i < V; i++) {
        if (disc[i] == -1) {
            APUtil(i, &time);
        }
    }

    return 0;
}

Hint

Use DFS recursion with discovery and low times. Update articulation points based on conditions for root and non-root nodes.

4

Print all articulation points

Add a for loop in main to print all vertices i where ap[i] == 1. Print them in the format: "Articulation Point: i\n".

DSA C

#include 
#include 

int V = 5;
int* adj[5];
int adj_size[5] = {0};

void add_edge(int u, int v) {
    adj[u][adj_size[u]++] = v;
    adj[v][adj_size[v]++] = u;
}

int disc[5];
int low[5];
int parent[5];
int ap[5];

void APUtil(int u, int* time) {
    disc[u] = low[u] = ++(*time);
    int children = 0;

    for (int i = 0; i  1)
                ap[u] = 1;

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

int main() {
    for (int i = 0; i < V; i++) {
        adj[i] = (int*)malloc(5 * sizeof(int));
    }

    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 2);
    add_edge(1, 3);
    add_edge(3, 4);

    for (int i = 0; i < V; i++) {
        disc[i] = -1;
        low[i] = -1;
        parent[i] = -1;
        ap[i] = 0;
    }

    int time = 0;
    for (int i = 0; i < V; i++) {
        if (disc[i] == -1) {
            APUtil(i, &time);
        }
    }

    // Print articulation points
    // Your code here

    return 0;
}

Hint

Loop through ap array and print all indices where value is 1.

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