Articulation Points in Graph in DSA C++ - Execution Trace

Concept Flow - Articulation Points in Graph

Start DFS at a node

↓

Mark node visited, set discovery & low time

↓

For each neighbor

↓

If neighbor not visited

↓

Recurse DFS

↓

Check articulation condition

↓

Mark articulation point if condition met

↓

Backtrack to parent

↓

Repeat for all nodes

↓

Output all articulation points

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

Execution Sample

DSA C++

void APUtil(int u, vector<int> adj[], vector<bool> &visited,
            vector<int> &disc, vector<int> &low, vector<int> &parent,
            vector<bool> &ap, int &time) {
    visited[u] = true;
    disc[u] = low[u] = ++time;
    int children = 0;
    for (int v : adj[u]) {
        if (!visited[v]) {
            children++;
            parent[v] = u;
            APUtil(v, adj, visited, disc, low, parent, ap, time);
            low[u] = 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] = min(low[u], disc[v]);
        }
    }
}

This code runs DFS to find articulation points by tracking discovery and low times, and marking nodes that satisfy articulation conditions.

Execution Table

Step	Operation	Current Node (u)	Neighbor (v)	Visited Set	Discovery Times	Low Times	Parent Array	Articulation Points	Visual State
1	Start DFS	0	-	[0]	[0:1]	[0:1]	[-1]	[false,false,false,false,false,false]	0(1)
2	Visit neighbor	0	1	[0,1]	[0:1,1:2]	[0:1,1:2]	[-1,0]	[false,false,false,false,false,false]	0(1)->1(2)
3	Visit neighbor	1	2	[0,1,2]	[0:1,1:2,2:3]	[0:1,1:2,2:3]	[-1,0,1]	[false,false,false,false,false,false]	0(1)->1(2)->2(3)
4	Backtrack	2	-	[0,1,2]	[0:1,1:2,2:3]	[0:1,1:2,2:3]	[-1,0,1]	[false,false,false,false,false,false]	0(1)->1(2)->2(3)
5	Update low of 1	1	2	[0,1,2]	[0:1,1:2,2:3]	[0:1,1:2,2:3]	[-1,0,1]	[false,true,false,false,false,false]	0(1)->1(2)->2(3)
6	Visit neighbor	1	3	[0,1,2,3]	[0:1,1:2,2:3,3:4]	[0:1,1:2,2:3,3:4]	[-1,0,1,1]	[false,true,false,false,false,false]	0(1)->1(2)->2(3),3(4)
7	Backtrack	3	-	[0,1,2,3]	[0:1,1:2,2:3,3:4]	[0:1,1:2,2:3,3:4]	[-1,0,1,1]	[false,true,false,false,false,false]	0(1)->1(2)->2(3),3(4)
8	Update low of 1	1	3	[0,1,2,3]	[0:1,1:2,2:3,3:4]	[0:1,1:2,2:3,3:4]	[-1,0,1,1]	[false,true,false,false,false,false]	0(1)->1(2)->2(3),3(4)
9	Backtrack	1	-	[0,1,2,3]	[0:1,1:2,2:3,3:4]	[0:1,1:2,2:3,3:4]	[-1,0,1,1]	[false,true,false,false,false,false]	0(1)->1(2)->2(3),3(4)
10	Update low of 0	0	1	[0,1,2,3]	[0:1,1:2,2:3,3:4]	[0:1,1:2,2:3,3:4]	[-1,0,1,1]	[false,true,false,false,false,false]	0(1)->1(2)->2(3),3(4)
11	Visit neighbor	0	4	[0,1,2,3,4]	[0:1,1:2,2:3,3:4,4:5]	[0:1,1:2,2:3,3:4,4:5]	[-1,0,1,1,0]	[false,true,false,false,false,false]	0(1)->1(2)->2(3),3(4),4(5)
12	Visit neighbor	4	5	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:2,2:3,3:4,4:5,5:6]	[-1,0,1,1,0,4]	[false,true,false,false,false,false]	0(1)->1(2)->2(3),3(4),4(5)->5(6)
13	Backtrack	5	-	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:2,2:3,3:4,4:5,5:6]	[-1,0,1,1,0,4]	[false,true,false,false,false,false]	0(1)->1(2)->2(3),3(4),4(5)->5(6)
14	Update low of 4	4	5	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:2,2:3,3:4,4:5,5:6]	[-1,0,1,1,0,4]	[false,true,false,false,false,false]	0(1)->1(2)->2(3),3(4),4(5)->5(6)
15	Backtrack	4	-	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:2,2:3,3:4,4:5,5:6]	[-1,0,1,1,0,4]	[false,true,false,false,false,false]	0(1)->1(2)->2(3),3(4),4(5)->5(6)
16	Update low of 0	0	4	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:2,2:3,3:4,4:5,5:6]	[-1,0,1,1,0,4]	[true,true,false,false,false,false]	0(1)->1(2)->2(3),3(4),4(5)->5(6)
17	End DFS	-	-	[0,1,2,3,4,5]	[0:1,1:2,2:3,3:4,4:5,5:6]	[0:1,1:2,2:3,3:4,4:5,5:6]	[-1,0,1,1,0,4]	[true,true,false,false,false,false]	Final articulation points: 0,1

💡 All nodes visited, DFS complete, articulation points identified

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 10	After Step 16	Final
visited	[false,false,false,false,false,false]	[true,false,false,false,false,false]	[true,true,true,true,false,false]	[true,true,true,true,true,false]	[true,true,true,true,true,true]	[true,true,true,true,true,true]
disc	[-1,-1,-1,-1,-1,-1]	[1,-1,-1,-1,-1,-1]	[1,2,3,4,-1,-1]	[1,2,3,4,5,-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,2,3,4,-1,-1]	[1,2,3,4,5,-1]	[1,2,3,4,5,6]	[1,2,3,4,5,6]
parent	[-1,-1,-1,-1,-1,-1]	[-1,-1,-1,-1,-1,-1]	[-1,0,1,1,-1,-1]	[-1,0,1,1,0,-1]	[-1,0,1,1,0,4]	[-1,0,1,1,0,4]
ap	[false,false,false,false,false,false]	[false,false,false,false,false,false]	[false,true,false,false,false,false]	[false,true,false,false,false,false]	[true,true,false,false,false,false]	[true,true,false,false,false,false]

Key Moments - 3 Insights

Why do we check if parent[u] == -1 and children > 1 to mark articulation point?

Because the root node of DFS tree is an articulation point only if it has more than one child subtree. This is shown in execution_table row 16 where node 0 is marked after having two children.

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

This updates low[u] to the earliest discovered ancestor reachable through back edge, preventing false articulation marking. See execution_table row 5 where low times are updated using disc values.

Why is a node marked articulation if low[v] >= disc[u] for non-root nodes?

Because it means the subtree rooted at v cannot reach an ancestor of u, so removing u disconnects the graph. This is shown in execution_table row 5 where node 1 is marked articulation.

Visual Quiz - 3 Questions

Look at the execution_table at step 16, which node is marked as an articulation point?

A Node 0

B Node 1

C Node 2

D Node 3

💡 Hint

Check the 'Articulation Points' column at step 16 in execution_table

At which step does node 1 get marked as an articulation point?

A Step 8

B Step 5

C Step 12

D Step 16

💡 Hint

Look at the 'Articulation Points' column and find when node 1 changes to true

If node 0 had only one child, how would the articulation points change?

A Node 0 would still be an articulation point

B Node 1 would not be an articulation point

C Node 0 would not be an articulation point

D All nodes would be articulation points

💡 Hint

Refer to the key moment about root node articulation condition and execution_table step 16

Concept Snapshot

Articulation Points in Graph:
- Use DFS to assign discovery and low times
- low[u] = earliest visited vertex reachable from u
- Root is articulation if it has >1 child
- Non-root u is articulation if low[v] >= disc[u] for any child v
- Helps find critical nodes disconnecting graph

Full Transcript

Articulation points are nodes in a graph that, if removed, increase the number of connected components. We find them using DFS by tracking discovery times and low values. The low value of a node is the earliest discovered node reachable from it or its descendants. The root node is an articulation point if it has more than one child in the DFS tree. For other nodes, if any child's low value is greater or equal to the node's discovery time, the node is an articulation point. This process is done by recursively visiting nodes, updating low values, and marking articulation points during backtracking.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex with the highest degree in the graph

B. A vertex which, when removed, increases the number of connected components

C. A vertex connected to all other vertices

D. A vertex that forms a cycle with its neighbors

Solution

1. Step 1: Understand the role of articulation points

   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 which, when removed, increases the number of connected components describes this property correctly; others describe different vertex properties.

3. Final Answer:

   A vertex which, when removed, increases the number of connected components -> Option B

4. Quick Check:

   Articulation point = vertex increasing components when removed [OK]

Hint: Articulation point breaks graph connectivity when removed [OK]

Common Mistakes:

• Confusing articulation point with highest degree vertex
• Thinking articulation point forms cycles
• Assuming articulation point connects to all vertices

2. Which of the following is the correct way to declare a vector of vectors for adjacency list in C++?

easy

A. vector adj;

B. vector adj<int>;

C. vector<int> adj[];

D. vector<vector> adj<int>;

Solution

1. Step 1: Recall correct syntax for 2D vector declaration

   In C++, a vector of vectors is declared as vector name; to represent adjacency lists.

2. Step 2: Check each option

   vector adj; matches correct syntax; A, B and D have syntax errors.

3. Final Answer:

   vector adj; -> Option A

4. Quick Check:

   2D vector syntax = vector [OK]

Hint: Use vector for adjacency lists in C++ [OK]

Common Mistakes:

• Using array syntax instead of vector
• Incorrect template syntax
• Missing angle brackets for nested vectors

3. Consider the following code snippet for finding articulation points in a graph with 4 vertices (0 to 3):

int timer = 0;
vector<int> disc(4, -1), low(4, -1);
vector<bool> visited(4, false), isAP(4, false);
vector adj = {{1, 2}, {0, 2}, {0, 1, 3}, {2}};

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

dfs(0, -1);

vector<int> result;
for (int i = 0; i < 4; i++) {
    if (isAP[i]) result.push_back(i);
}
for (int x : result) cout << x << " ";

What will be the output?

medium

A. 2

B. 0 1 2

C. 1 2

D. 0 2

Solution

1. Step 1: Analyze the graph structure and DFS traversal

   The graph edges are: 0-1, 0-2, 1-2, 2-3 (triangle 0-1-2 + pendant 3 on 2). DFS from 0 visits 1 then 2 then 3; when back to 0, 2 already visited so root children=1 (not AP).

2. Step 2: Check articulation point conditions in code

   Root children=1 (<=1, not AP). For non-root u=2 (parent=1), low[3]=3 >= disc[2]=2 so isAP[2]=true. No others. Output is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Root children=1 and vertex 2 disconnects 3 = 2 [OK]

Hint: Root with >1 child and low[v]>=disc[u] mark AP [OK]

Common Mistakes:

• Missing root articulation point condition
• Confusing low and disc arrays
• Ignoring parent check in DFS

4. The following code snippet is intended to find articulation points but has a bug:

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

What is the bug in this code?

medium

A. Not marking visited[u] as true at start

B. Incorrect update of low[u] inside else if block

C. Not incrementing timer before assigning disc[u]

D. Missing check for parent != -1 before marking isAP[u]

Solution

1. Step 1: Understand articulation point condition for non-root nodes

   For non-root nodes, isAP[u] should be set only if parent != -1 and low[v] >= disc[u]. The code misses the parent != -1 check before setting isAP[u].

2. Step 2: Verify other parts of code

   Timer is incremented correctly, visited[u] is set true, low[u] updated properly. So only missing parent check is the bug.

3. Final Answer:

   Missing check for parent != -1 before marking isAP[u] -> Option D

4. Quick Check:

   Parent check needed before marking articulation point [OK]

Hint: Add parent != -1 check before marking articulation point [OK]

Common Mistakes:

• Marking root as articulation point incorrectly
• Confusing order of visited and timer increment
• Ignoring parent in back edge condition

5. Given 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

B. 0 1 3

C. 1 3

D. 3 4

Solution

1. Step 1: Analyze graph connectivity and removal effects

   Vertices 0,1,2 form a triangle (cycle), so none of them alone disconnects graph except vertex 1 which connects to 3 and 4. Removing 1 disconnects 3 and 4. Removing 3 disconnects 4. So 1 and 3 are articulation points.

2. Step 2: Confirm articulation points

   Vertex 1 connects two parts: cycle and chain (3-4). Vertex 3 connects 4 only. Removing 1 or 3 increases components. Vertex 0, 2, 4 are not articulation points.

3. Final Answer:

   1 3 -> Option C

4. Quick Check:

   Removing 1 or 3 disconnects graph = 1 3 [OK]

Hint: Check if removing vertex splits graph into parts [OK]

Common Mistakes:

• Including vertices in cycles as articulation points
• Missing leaf node articulation points
• Confusing articulation points with bridges