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 neighbor

↓

If neighbor not visited

↓

DFS on neighbor

↓

Update low[node

↓

Check articulation conditions

↓

Mark node as articulation if condition met

↓

If neighbor visited and not parent

↓

Update low[node

↓

Repeat for all neighbors

↓

End DFS for node

↓

Repeat DFS for all unvisited nodes

↓

Collect all articulation points

↓

Done

The algorithm uses DFS to visit nodes, tracks discovery and low times, and marks nodes as articulation points when removing them increases graph components.

Execution Sample

DSA C#

void APUtil(int u, bool[] visited, int[] disc, int[] low, int[] parent, bool[] ap) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  int children = 0;
  foreach (int v in graph[u]) {
    if (!visited[v]) {
      children++;
      parent[v] = u;
      APUtil(v, visited, disc, low, parent, ap);
      low[u] = Math.Min(low[u], low[v]);
      if (parent[u] == -1 && children > 1) ap[u] = true;
      if (parent[u] != -1 && low[v] >= disc[u]) ap[u] = true;
    } else if (v != parent[u]) {
      low[u] = Math.Min(low[u], disc[v]);
    }
  }
}

This code runs DFS to find articulation points by updating discovery and low times and checking conditions for articulation.

Execution Table

Step	Operation	Node Visited	Discovery Time (disc)	Low Time (low)	Parent	Children Count	Articulation Point Marked	Graph State (Edges)	Visual State
1	Start DFS at node 0	0	0	0	-1	0	No	0: [1,2]	0(disc=0, low=0)
2	Visit neighbor 1 of 0	1	1	1	0	0	No	1: [0,2,3]	0(disc=0, low=0) -> 1(disc=1, low=1)
3	Visit neighbor 2 of 1	2	2	2	1	0	No	2: [0,1]	0(disc=0, low=0) -> 1(disc=1, low=1) -> 2(disc=2, low=2)
4	Neighbor 0 visited and is parent of 1, skip	2	2	2	1	0	No		No change
5	Back to node 1, update low[1] = min(1, low[2]=2) = 1	1	1	1	0	1	No		low[1]=1
6	Visit neighbor 3 of 1	3	3	3	1	0	No	3: [1,4]	Add 3(disc=3, low=3)
7	Visit neighbor 4 of 3	4	4	4	3	0	No	4: [3]	Add 4(disc=4, low=4)
8	Back to node 3, update low[3] = min(3, low[4]=4) = 3	3	3	3	1	1	No		low[3]=3
9	Back to node 1, update low[1] = min(1, low[3]=3) = 1	1	1	1	0	2	No		low[1]=1, children=2
10	Check articulation for node 1 (parent=0, children=2 >1) => mark AP	1	1	1	0	2	Yes		Node 1 marked AP
11	Back to node 0, update low[0] = min(0, low[1]=1) = 0	0	0	0	-1	1	No		low[0]=0, children=1
12	Visit neighbor 2 of 0 (already visited)	0	0	0	-1	1	No		No change
13	DFS complete for node 0	0	0	0	-1	1	No		End DFS at 0
14	Start DFS at node 5 (unvisited)	5	5	5	-1	0	No	5: [6]	Add 5(disc=5, low=5)
15	Visit neighbor 6 of 5	6	6	6	5	0	No	6: [5]	Add 6(disc=6, low=6)
16	Back to node 5, update low[5] = min(5, low[6]=6) = 5	5	5	5	-1	1	No		low[5]=5, children=1
17	DFS complete for node 5	5	5	5	-1	1	No		End DFS at 5
18	Collect articulation points: node 1	-	-	-	-	-	Yes	-	Articulation points: [1]
19	DFS complete for all nodes	-	-	-	-	-	-	-	Done

💡 All nodes visited, DFS complete, articulation points identified

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	After Step 10	After Step 14	After Step 18	Final
visited	[false,false,false,false,false,false,false]	[true,false,false,false,false,false,false]	[true,true,false,false,false,false,false]	[true,true,true,false,false,false,false]	[true,true,true,true,false,false,false]	[true,true,true,true,false,false,false]	[true,true,true,true,false,true,false]	[true,true,true,true,false,true,true]	[true,true,true,true,false,true,true]
disc	[-1,-1,-1,-1,-1,-1,-1]	[0,-1,-1,-1,-1,-1,-1]	[0,1,-1,-1,-1,-1,-1]	[0,1,2,-1,-1,-1,-1]	[0,1,2,3,-1,-1,-1]	[0,1,2,3,-1,-1,-1]	[0,1,2,3,-1,5,-1]	[0,1,2,3,-1,5,6]	[0,1,2,3,-1,5,6]
low	[-1,-1,-1,-1,-1,-1,-1]	[0,-1,-1,-1,-1,-1,-1]	[0,1,-1,-1,-1,-1,-1]	[0,1,2,-1,-1,-1,-1]	[0,1,2,3,-1,-1,-1]	[0,1,2,3,-1,-1,-1]	[0,1,2,3,-1,5,-1]	[0,1,2,3,-1,5,6]	[0,1,2,3,-1,5,6]
parent	[-1,-1,-1,-1,-1,-1,-1]	[-1,-1,-1,-1,-1,-1,-1]	[-1,0,-1,-1,-1,-1,-1]	[-1,0,1,-1,-1,-1,-1]	[-1,0,1,1,-1,-1,-1]	[-1,0,1,1,-1,-1,-1]	[-1,0,1,1,-1,-1,-1]	[-1,0,1,1,-1,-1,-1]	[-1,0,1,1,-1,-1,-1]
children	0	0	0	0	2	2	0	0	0
ap	[false,false,false,false,false,false,false]	[false,false,false,false,false,false,false]	[false,false,false,false,false,false,false]	[false,false,false,false,false,false,false]	[false,false,false,false,false,false,false]	[false,true,false,false,false,false,false]	[false,true,false,false,false,false,false]	[false,true,false,false,false,false,false]	[false,true,false,false,false,false,false]

Key Moments - 3 Insights

Why do we mark a node as articulation point only if it has more than one child when it is the root?

Because the root node is an articulation point only if removing it disconnects the graph into multiple parts. This happens when it has more than one child in DFS tree, as shown in execution_table row 10 where node 1 is root with 2 children and marked AP.

Why do we update low[u] with disc[v] when neighbor v is already visited and not parent?

This update helps to find back edges to ancestors, lowering the low value. It ensures we track the earliest visited node reachable. See execution_table row 4 where low is updated using disc of visited neighbor.

Why do we check low[v] >= disc[u] to mark articulation points for non-root nodes?

Because if low[v] >= disc[u], it means no back edge from v or its descendants to ancestors of u, so removing u disconnects v's subtree. This condition is checked in execution_table row 10 for node 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, why is node 1 marked as an articulation point?

A Because it has more than one child and is root

B Because it has no children

C Because low[child] >= disc[node] and it has multiple children

D Because it is a leaf node

💡 Hint

Check 'Children Count' and 'Articulation Point Marked' columns at step 10 in execution_table

At which step does the DFS start for the disconnected component containing node 5?

A Step 14

B Step 1

C Step 10

D Step 18

💡 Hint

Look for 'Start DFS at node 5' operation in execution_table

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

A It would still be marked as articulation point

B It would not be marked as articulation point

C It would be marked only if low[child] < disc[node]

D It would be marked only if it is a leaf

💡 Hint

Refer to articulation condition for root nodes in key_moments and execution_table step 10

Concept Snapshot

Articulation Points in Graph:
- Use DFS to assign discovery and low times
- low[u] = earliest visited reachable node from u
- Root with >1 child is articulation point
- Non-root u is articulation if low[v] >= disc[u] for child v
- Helps find nodes whose removal disconnects graph

Full Transcript

Articulation points are nodes in a graph which, if removed, increase the number of connected components. We use a DFS traversal to assign each node a discovery time and a low value, which tracks the earliest visited node reachable from that node or its descendants. During DFS, for each node, we check if it is a root with more than one child or if any child's low value is greater or equal to the node's discovery time. If so, that node is an articulation point. The execution table shows step-by-step DFS visits, updates of discovery and low times, parent-child relationships, and marking of articulation points. The variable tracker records the state of visited nodes, discovery and low arrays, parents, children count, and articulation point flags after each step. Key moments clarify why root nodes need multiple children to be articulation points, why low values are updated with discovery times of visited neighbors, and the condition for non-root articulation points. The visual quiz tests understanding of these steps and conditions. This method helps identify critical nodes in network connectivity.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex that forms a cycle with other vertices

B. A vertex with the highest degree in the graph

C. A vertex that has no edges connected to it

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

Solution

1. Step 1: Understand the definition of articulation point

   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 D

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 a vertex with no edges
• Mixing articulation point with cycle formation

2. Which of the following is the correct C# method signature to find articulation points in a graph represented as adjacency list?

easy

A. public void FindArticulationPoints(List<int>[] graph, int vertices)

B. public int FindArticulationPoints(int[][] graph)

C. public bool FindArticulationPoints(Dictionary graph)

D. public void FindArticulationPoints(int[] graph, int vertices)

Solution

1. Step 1: Identify common graph representation in C#

   Adjacency list is often represented as List<int>[] for vertices count known.

2. Step 2: Check method signature compatibility

   public void FindArticulationPoints(List<int>[] graph, int vertices) uses List<int>[] and vertices count, suitable for articulation point algorithm.

3. Final Answer:

   public void FindArticulationPoints(List<int>[] graph, int vertices) -> Option A

4. Quick Check:

   Adjacency list with vertex count = correct signature [OK]

Hint: Use List<int>[] and vertex count for adjacency list [OK]

Common Mistakes:

• Using 2D array instead of adjacency list
• Returning int or bool instead of void
• Using Dictionary without vertex count parameter

3. Given the following graph edges:
0 - 1, 1 - 2, 2 - 0, 1 - 3
Which vertex is an articulation point?

medium

A. Vertex 0

B. Vertex 3

C. Vertex 1

D. Vertex 2

Solution

1. Step 1: Visualize the graph connections

   Vertices 0,1,2 form a triangle (cycle). Vertex 3 connects only to 1.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects vertex 3 from the rest, increasing components. Others do not disconnect graph.

3. Final Answer:

   Vertex 1 -> Option C

4. Quick Check:

   Removing vertex 1 splits graph = articulation point [OK]

Hint: Check if removing vertex disconnects graph [OK]

Common Mistakes:

• Assuming all vertices in cycle are articulation points
• Ignoring leaf vertex connections
• Confusing vertex numbers

4. Consider this C# code snippet to find articulation points:

void DFS(int u, int parent) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  int children = 0;
  foreach(var v in graph[u]) {
    if (!visited[v]) {
      children++;
      DFS(v, u);
      low[u] = Math.Min(low[u], low[v]);
      if (parent != -1 && low[v] >= disc[u])
        articulation[u] = true;
    } else if (v != parent) {
      low[u] = Math.Min(low[u], disc[v]);
    }
  }
  if (parent == -1 && children > 1)
    articulation[u] = true;
}

What is the bug in this code?

medium

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

B. The variable 'time' is not initialized or incremented properly

C. The check 'v != parent' is incorrect and should be removed

D. The articulation array should be reset inside DFS

Solution

1. Step 1: Analyze usage of 'time' variable

   'time' is used to assign discovery times but code snippet does not show initialization or global declaration.

2. Step 2: Check other conditions

   Conditions and logic for articulation points are correct; 'time' must be properly initialized and incremented outside DFS.

3. Final Answer:

   The variable 'time' is not initialized or incremented properly -> Option B

4. Quick Check:

   Uninitialized 'time' breaks discovery time tracking [OK]

Hint: Initialize and increment 'time' outside DFS [OK]

Common Mistakes:

• Changing correct condition to strict inequality
• Removing parent check causing wrong low updates
• Resetting articulation inside DFS causing wrong results

5. You have a connected graph with 5 vertices and edges:
0-1, 1-2, 2-0, 1-3, 3-4
Which vertices are articulation points?

hard

A. [1, 3]

B. [0, 2]

C. [3, 4]

D. [1, 4]

Solution

1. Step 1: Visualize the graph structure

   Vertices 0,1,2 form a triangle. Vertex 3 connects to 1 and 4. Vertex 4 is leaf.

2. Step 2: Identify articulation points

   Removing 1 disconnects 3 and 4. Removing 3 disconnects 4. Vertices 0,2 are in cycle, not articulation points. Vertex 4 is leaf, not articulation.

3. Final Answer:

   [1, 3] -> Option A

4. Quick Check:

   Vertices disconnecting graph when removed = [1, 3] [OK]

Hint: Check vertices whose removal disconnects others [OK]

Common Mistakes:

• Including leaf vertex as articulation point
• Confusing cycle vertices as articulation points
• Missing vertex 3 as articulation point