Articulation Points in Graph in DSA C - Execution Trace

Concept Flow - Articulation Points in Graph

Start DFS from a node

↓

Mark node visited, set discovery & low time

↓

For each adjacent node

↓

If not visited

↓

Recurse DFS

↓

Check articulation conditions

↓

Mark articulation point if conditions met

↓

Repeat for all nodes

↓

End: All articulation points found

This flow shows how DFS visits nodes, updates discovery and low times, and identifies articulation points by checking conditions during traversal.

Execution Sample

DSA C

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

This code runs DFS from node u, tracks discovery and low times, counts children, and marks articulation points.

Execution Table

Step	Operation	Current Node	Visited Nodes	Discovery Times	Low Times	Articulation Points	Stack/Call
1	Start DFS	0	[0]	[0:1]	[0:1]	[]	[Call APUtil(0)]
2	Visit neighbor 1	1	[0,1]	[0:1,1:2]	[0:1,1:2]	[]	[Call APUtil(1)]
3	Visit neighbor 2	2	[0,1,2]	[0:1,1:2,2:3]	[0:1,1:2,2:3]	[]	[Call APUtil(2)]
4	Backtrack from 2	1	[0,1,2]	[0:1,1:2,2:3]	[0:1,1:2,2:3]	[]	[Return from APUtil(2)]
5	Update low[1]	1	[0,1,2]	[0:1,1:2,2:3]	[0:1,1:1,2:3]	[]	[In APUtil(1)]
6	Visit neighbor 3	3	[0,1,2,3]	[0:1,1:2,2:3,3:4]	[0:1,1:1,2:3,3:4]	[]	[Call APUtil(3)]
7	Backtrack from 3	1	[0,1,2,3]	[0:1,1:2,2:3,3:4]	[0:1,1:1,2:3,3:4]	[]	[Return from APUtil(3)]
8	Update low[1]	1	[0,1,2,3]	[0:1,1:2,2:3,3:4]	[0:1,1:1,2:3,3:4]	[]	[In APUtil(1)]
9	Check articulation at 1	1	[0,1,2,3]	[0:1,1:2,2:3,3:4]	[0:1,1:1,2:3,3:4]	[1]	[In APUtil(1)]
10	Backtrack from 1	0	[0,1,2,3]	[0:1,1:2,2:3,3:4]	[0:1,1:1,2:3,3:4]	[1]	[Return from APUtil(1)]
11	Update low[0]	0	[0,1,2,3]	[0:1,1:2,2:3,3:4]	[0:1,1:1,2:3,3:4]	[1]	[In APUtil(0)]
12	Visit neighbor 4	4	[0,1,2,3,4]	[0:1,1:2,2:3,3:4,4:5]	[0:1,1:1,2:3,3:4,4:5]	[1]	[Call APUtil(4)]
13	Visit neighbor 5	5	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:1,2:3,3:4,4:5,5:6]	[1]	[Call APUtil(5)]
14	Backtrack from 5	4	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:1,2:3,3:4,4:5,5:6]	[1]	[Return from APUtil(5)]
15	Update low[4]	4	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:1,2:3,3:4,4:5,5:6]	[1]	[In APUtil(4)]
16	Backtrack from 4	0	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:1,2:3,3:4,4:5,5:6]	[1,0]	[Return from APUtil(4)]
17	Update low[0]	0	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:1,2:3,3:4,4:5,5:6]	[1,0]	[In APUtil(0)]
18	Check articulation at 0	0	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:1,2:3,3:4,4:5,5:6]	[1,0]	[In APUtil(0)]
19	End DFS	-	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:1,2:3,3:4,4:5,5:6]	[1,0]	[]

💡 All nodes visited, DFS complete, articulation points identified

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 9	After Step 16	Final
visited	[]	[0]	[0,1,2,3]	[0,1,2,3]	[0,1,2,3,4,5]	[0,1,2,3,4,5]
disc	[-1,-1,-1,-1,-1,-1]	[1,-1,-1,-1,-1,-1]	[1,2,3,4,-1,-1]	[1,2,3,4,-1,-1]	[1,2,3,4,5,6]	[1,2,3,4,5,6]
low	[-1,-1,-1,-1,-1,-1]	[1,-1,-1,-1,-1,-1]	[1,1,3,4,-1,-1]	[1,1,3,4,-1,-1]	[1,1,3,4,5,6]	[1,1,3,4,5,6]
articulation_points	[]	[]	[]	[1]	[]	[1,0]

Key Moments - 3 Insights

Why do we update low[u] with low[v] after visiting a child v?

Because low[u] tracks the earliest visited node reachable from u or its descendants. Updating low[u] with low[v] (see step 5 and 8) helps detect if there's a back edge connecting v or its subtree to an ancestor of u.

Why is node 0 marked as an articulation point at step 18?

Node 0 is the root of DFS and has more than one child in the DFS tree (steps 1 and 16). This means removing it disconnects the graph, so it is an articulation point.

Why do we check if low[v] >= disc[u] to mark u as articulation point?

Because if low[v] (earliest reachable ancestor from v) is not less than disc[u], it means v and its subtree cannot reach an ancestor of u without going through u, so u is critical (see step 9).

Visual Quiz - 3 Questions

Look at the execution table at step 9, which node is identified as an articulation point?

A Node 1

B Node 0

C Node 2

D Node 3

💡 Hint

Check the 'Articulation Points' column at step 9 in the execution table.

At which step does the DFS finish visiting all nodes?

A Step 16

B Step 19

C Step 12

D Step 5

💡 Hint

Look at the 'Operation' column for the step indicating 'End DFS' in the execution table.

If node 0 had only one child in DFS, what would happen to its articulation point status?

A It would depend on low values of children

B It would still be an articulation point

C It would not be an articulation point

D It would be marked only if it has back edges

💡 Hint

Refer to the key moment about root node articulation condition and step 18.

Concept Snapshot

Articulation Points in Graph:
- Use DFS to assign discovery and low times
- low[u] = earliest visited node reachable from u or descendants
- Node u is articulation if:
  * u is root with >1 child
  * low[v] >= disc[u] for child v
- Helps find critical nodes disconnecting graph
- Runs in O(V+E) time using DFS

Full Transcript

Articulation points are nodes in a graph which, if removed, increase the number of connected components. We find them using DFS traversal. Each node gets a discovery time and a low time. The low time tells the earliest visited node reachable from that node or its descendants. During DFS, if a child node cannot reach an ancestor of the current node, the current node is an articulation point. The root node is special: if it has more than one child, it is an articulation point. This method helps identify critical nodes that keep the graph connected. The process runs efficiently in linear time relative to nodes and edges.

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