Articulation Points in Graph in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of articulation points detection in a simple graph

What is the output of the following code that finds articulation points in the given graph?

DSA C

/* Graph edges: 0-1, 1-2, 2-0, 1-3 */
#include <stdio.h>
#include <stdlib.h>
#define V 4

int time_counter = 0;

void APUtil(int u, int visited[], int disc[], int low[], int parent[], int ap[], int graph[V][V]) {
    visited[u] = 1;
    disc[u] = low[u] = ++time_counter;
    int children = 0;
    for (int v = 0; v < V; v++) {
        if (graph[u][v]) {
            if (!visited[v]) {
                children++;
                parent[v] = u;
                APUtil(v, visited, disc, low, parent, ap, graph);
                if (parent[u] == -1 && children > 1)
                    ap[u] = 1;
                if (parent[u] != -1 && low[v] >= disc[u])
                    ap[u] = 1;
                if (low[v] < low[u])
                    low[u] = low[v];
            } else if (v != parent[u]) {
                if (disc[v] < low[u])
                    low[u] = disc[v];
            }
        }
    }
}

void AP(int graph[V][V]) {
    int visited[V] = {0}, disc[V], low[V], parent[V], ap[V] = {0};
    for (int i = 0; i < V; i++) parent[i] = -1;
    for (int i = 0; i < V; i++) {
        if (!visited[i])
            APUtil(i, visited, disc, low, parent, ap, graph);
    }
    printf("Articulation points: ");
    for (int i = 0; i < V; i++) {
        if (ap[i]) printf("%d ", i);
    }
    printf("\n");
}

int main() {
    int graph[V][V] = {
        {0,1,1,0},
        {1,0,1,1},
        {1,1,0,0},
        {0,1,0,0}
    };
    AP(graph);
    return 0;
}

A Articulation points: 2 3

B Articulation points: 1

C Articulation points: 3

D Articulation points: 0 1

💡 Hint

Focus on the node whose removal increases the number of connected components.

Node 1 is the only articulation point because removing it disconnects node 3 from the rest.

🧠 Conceptual

intermediate

Understanding articulation points in a tree

In a tree with 5 nodes connected as 0-1, 1-2, 1-3, 3-4, which nodes are articulation points?

A Nodes 0 and 4

B Nodes 2 and 4

C Nodes 1 and 3

D Nodes 0, 2, and 4

💡 Hint

Articulation points are nodes which, when removed, increase the number of connected components.

Removing node 1 disconnects nodes 0, 2, and 3-4 parts. Removing node 3 disconnects node 4.

🔧 Debug

advanced

Identify the error in articulation points code

What error will the following code produce when run on a graph with 3 nodes connected linearly (0-1-2)?

DSA C

#include <stdio.h>
#define V 3

int time = 0;

void APUtil(int u, int visited[], int disc[], int low[], int parent[], int ap[], int graph[V][V]) {
    visited[u] = 1;
    disc[u] = low[u] = ++time;
    int children = 0;
    for (int v = 0; v < V; v++) {
        if (graph[u][v]) {
            if (!visited[v]) {
                children++;
                parent[v] = u;
                APUtil(v, visited, disc, low, parent, ap, graph);
                if (low[v] >= disc[u])
                    ap[u] = 1;
                if (low[v] < low[u])
                    low[u] = low[v];
            } else if (v != parent[u]) {
                if (disc[v] < low[u])
                    low[u] = disc[v];
            }
        }
    }
}

void AP(int graph[V][V]) {
    int visited[V] = {0}, disc[V], low[V], parent[V], ap[V] = {0};
    for (int i = 0; i < V; i++) parent[i] = -1;
    for (int i = 0; i < V; i++) {
        if (!visited[i])
            APUtil(i, visited, disc, low, parent, ap, graph);
    }
    printf("Articulation points: ");
    for (int i = 0; i < V; i++) {
        if (ap[i]) printf("%d ", i);
    }
    printf("\n");
}

int main() {
    int graph[V][V] = {
        {0,1,0},
        {1,0,1},
        {0,1,0}
    };
    AP(graph);
    return 0;
}

A Logical error: root node with one child incorrectly marked as articulation point

B No error, output: Articulation points: 0 1

C No error, output: Articulation points: 0

D No error, output: Articulation points: 1

💡 Hint

Check how root nodes with one child are handled in articulation point logic.

The code marks root nodes as articulation points if low[v] >= disc[u], but it misses the special case that root with only one child is not an articulation point.

❓ Predict Output

advanced

Output of articulation points in a complex graph

What is the output of the following code for articulation points in the graph with edges: 0-1, 1-2, 2-0, 1-3, 3-4, 4-5, 5-3?

DSA C

#include <stdio.h>
#define V 6

int time = 0;

void APUtil(int u, int visited[], int disc[], int low[], int parent[], int ap[], int graph[V][V]) {
    visited[u] = 1;
    disc[u] = low[u] = ++time;
    int children = 0;
    for (int v = 0; v < V; v++) {
        if (graph[u][v]) {
            if (!visited[v]) {
                children++;
                parent[v] = u;
                APUtil(v, visited, disc, low, parent, ap, graph);
                if (parent[u] == -1 && children > 1)
                    ap[u] = 1;
                if (parent[u] != -1 && low[v] >= disc[u])
                    ap[u] = 1;
                if (low[v] < low[u])
                    low[u] = low[v];
            } else if (v != parent[u]) {
                if (disc[v] < low[u])
                    low[u] = disc[v];
            }
        }
    }
}

void AP(int graph[V][V]) {
    int visited[V] = {0}, disc[V], low[V], parent[V], ap[V] = {0};
    for (int i = 0; i < V; i++) parent[i] = -1;
    for (int i = 0; i < V; i++) {
        if (!visited[i])
            APUtil(i, visited, disc, low, parent, ap, graph);
    }
    printf("Articulation points: ");
    for (int i = 0; i < V; i++) {
        if (ap[i]) printf("%d ", i);
    }
    printf("\n");
}

int main() {
    int graph[V][V] = {
        {0,1,1,0,0,0},
        {1,0,1,1,0,0},
        {1,1,0,0,0,0},
        {0,1,0,0,1,1},
        {0,0,0,1,0,1},
        {0,0,0,1,1,0}
    };
    AP(graph);
    return 0;
}

A Articulation points: 0 1 3

B Articulation points: 1

C Articulation points: 3

D Articulation points: 1 3

💡 Hint

Check root node with multiple children and nodes whose removal disconnects subgraphs.

Node 1 is an articulation point because removing it disconnects node 3 and its cycle. Node 3 is articulation point because removing it disconnects nodes 4 and 5.

🧠 Conceptual

expert

Minimum number of articulation points in a biconnected graph

What is the minimum number of articulation points in a biconnected graph with more than two vertices?

A Zero

B One

C Two

D Depends on the number of vertices

💡 Hint

Recall the definition of biconnected graph regarding articulation points.

A biconnected graph has no articulation points by definition.

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