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.