Log inSign up
hardGeeksforGeeksNot Started

Articulation Points

Given an undirected connected graph with V vertices and adjacency list adj. An articulation point (or cut vertex) is a vertex whose removal increases the number of connected components in the graph. Find all articulation points.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an undirected graph with V vertices numbered 0 to V-1 and an adjacency list adj.

An articulation point (or cut vertex) is a vertex whose removal (along with all edges incident to it) strictly increases the number of connected components in the graph.

Find all articulation points in the graph. If there are no articulation points, return [-1]. Return the vertices in sorted order.

Constraints:

  • 1 <= V <= 105
  • 0 <= E <= 105
  • Graph may contain disconnected components.
  • 0 <= u, v < V

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the mechanics of DFS tree forward edges and back edges in undirected graphs.
  • Master Tarjan's discovery time (tin) and low-link value (low) calculations.
  • Distinguish the two distinct cut-vertex rules: root with > 1 children vs non-root with low[v] >= tin[u].

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding single points of failure in a network.
  • Identifying vertices whose removal disconnects the graph.
  • Biconnectivity, cut-vertices, 2-vertex-connected components.

Algorithmic Decision Tree:

  • BRUTE FORCE: For every vertex v from 0 to V-1, temporarily remove v and count connected components via BFS/DFS -> O(V * (V + E)).
  • BETTER: Cycle detection and subtree size tracking on DFS tree without low array -> O(V2).
  • OPTIMAL: Tarjan's Algorithm tracking tin[u] and low[u] in a single DFS traversal -> O(V + E) time and O(V) space.

Connected Patterns:

Bridges in GraphTarjan's Strongly Connected ComponentsCritical Connections

1. Vertex Removal and Component Counting

Intuition

Count initial connected components. Then for each vertex i, ignore vertex i and count connected components of the remaining graph using BFS. If components increase, i is an articulation point.

Algorithm

  1. Count initial connected components in the graph with BFS.
  2. For each vertex i from 0 to V-1:
  3. Run BFS/DFS skipping vertex i. Count connected components among the remaining vertices.
  4. If remaining components > initial components, mark i as an articulation point.
  5. Return sorted articulation points, or [-1] if none found.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9 int countComponents(int V, const vector<vector<int>>& adj, int skip) {
10 vector<bool> visited(V, false);
11 int comps = 0;
12 for (int i = 0; i < V; ++i) {
13 if (i == skip || visited[i]) continue;
14 comps++;
15 queue<int> q;
16 q.push(i);
17 visited[i] = true;
18 while (!q.empty()) {
19 int u = q.front();
20 q.pop();
21 for (int v : adj[u]) {
22 if (v != skip && !visited[v]) {
23 visited[v] = true;
24 q.push(v);
25 }
26 }
27 }
28 }
29 return comps;
30 }
31
32public:
33 vector<int> articulationPoints(int V, vector<vector<int>>& adj) {
34 int initialComps = countComponents(V, adj, -1);
35 vector<int> result;
36 for (int i = 0; i < V; ++i) {
37 int comps = countComponents(V, adj, i);
38 if (comps > initialComps) {
39 result.push_back(i);
40 }
41 }
42 if (result.empty()) return {-1};
43 return result;
44 }
45};
46
47int main() {
48 int V = 5;
49 vector<vector<int>> adj(V);
50 vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}};
51 for (auto& e : edges) {
52 adj[e.first].push_back(e.second);
53 adj[e.second].push_back(e.first);
54 }
55 Solution solver;
56 vector<int> aps = solver.articulationPoints(V, adj);
57 for (int u : aps) cout << u << " ";
58 cout << endl;
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(V * (V + E))
  • Space complexity: O(V + E)

2. DFS Tree Cycle Detection with Reachability Set

Intuition

Construct a spanning DFS tree and for each vertex u and child v, verify if any node in the subtree rooted at v has a back edge to a proper ancestor of u.

Algorithm

  1. Run DFS to build the DFS tree and compute vertex depths.
  2. For each node u and each child v in the DFS tree, collect all reachable ancestors from v's subtree using back-edges.
  3. If the highest ancestor reachable from v's subtree has depth >= depth of u, then u separates v from the rest of the graph.
  4. Check root separately for >= 2 children in the DFS tree.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9 void dfs(int u, int p, int d, const vector<vector<int>>& adj,
10 vector<int>& depth, vector<vector<int>>& treeChildren, vector<vector<int>>& backEdges) {
11 depth[u] = d;
12 for (int v : adj[u]) {
13 if (v == p) continue;
14 if (depth[v] != -1) {
15 if (depth[v] < depth[u]) backEdges[u].push_back(v);
16 } else {
17 treeChildren[u].push_back(v);
18 dfs(v, u, d + 1, adj, depth, treeChildren, backEdges);
19 }
20 }
21 }
22
23 int getMinAncestorDepth(int u, const vector<vector<int>>& treeChildren,
24 const vector<vector<int>>& backEdges, const vector<int>& depth) {
25 int minD = depth[u];
26 for (int a : backEdges[u]) minD = min(minD, depth[a]);
27 for (int child : treeChildren[u]) {
28 minD = min(minD, getMinAncestorDepth(child, treeChildren, backEdges, depth));
29 }
30 return minD;
31 }
32
33public:
34 vector<int> articulationPoints(int V, vector<vector<int>>& adj) {
35 vector<int> depth(V, -1);
36 vector<vector<int>> treeChildren(V), backEdges(V);
37 vector<bool> isAp(V, false);
38
39 for (int i = 0; i < V; ++i) {
40 if (depth[i] == -1) {
41 dfs(i, -1, 0, adj, depth, treeChildren, backEdges);
42 if (treeChildren[i].size() > 1) isAp[i] = true;
43 }
44 }
45
46 for (int u = 0; u < V; ++u) {
47 if (depth[u] == 0) continue; // handled above
48 for (int v : treeChildren[u]) {
49 if (getMinAncestorDepth(v, treeChildren, backEdges, depth) >= depth[u]) {
50 isAp[u] = true;
51 break;
52 }
53 }
54 }
55
56 vector<int> res;
57 for (int i = 0; i < V; ++i) if (isAp[i]) res.push_back(i);
58 return res.empty() ? vector<int>{-1} : res;
59 }
60};
61
62int main() {
63 int V = 5;
64 vector<vector<int>> adj(V);
65 vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}};
66 for (auto& e : edges) {
67 adj[e.first].push_back(e.second);
68 adj[e.second].push_back(e.first);
69 }
70 Solution solver;
71 vector<int> aps = solver.articulationPoints(V, adj);
72 for (int u : aps) cout << u << " ";
73 cout << endl;
74 return 0;
75}

Time & Space Complexity

  • Time complexity: O(V^2)
  • Space complexity: O(V + E)

3. Tarjan's Algorithm (Discovery Time & Low-Link Values)

Intuition

Execute a single DFS pass maintaining tin[u] (discovery timestamp) and low[u] (lowest discovery time reachable via subtree and at most one back-edge). Check cut-vertex criteria in O(1) during post-order returns.

Algorithm

  1. Initialize tin and low arrays to -1, a timer = 0, and a boolean array isArticulation of size V.
  2. For every unvisited node i from 0 to V-1, invoke dfs(i, -1).
  3. In dfs(u, p):
  4. Set tin[u] = low[u] = ++timer and count DFS tree children = 0.
  5. For each neighbor v of u:
  6. If v == p, continue (ignore parent edge).
  7. If v is visited: update low[u] = min(low[u], tin[v]) (back-edge).
  8. If v is unvisited: increment children, recurse dfs(v, u), update low[u] = min(low[u], low[v]).
  9. If low[v] >= tin[u] and p != -1: mark isArticulation[u] = true.
  10. If p == -1 and children > 1: mark isArticulation[u] = true.
  11. Collect all indices where isArticulation[i] == true. Return [-1] if none exist.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int timer;
9 void dfs(int u, int p, const vector<vector<int>>& adj,
10 vector<int>& tin, vector<int>& low, vector<bool>& isAp) {
11 tin[u] = low[u] = ++timer;
12 int children = 0;
13
14 for (int v : adj[u]) {
15 if (v == p) continue;
16 if (tin[v] != -1) {
17 // Back-edge
18 low[u] = min(low[u], tin[v]);
19 } else {
20 children++;
21 dfs(v, u, adj, tin, low, isAp);
22 low[u] = min(low[u], low[v]);
23 if (low[v] >= tin[u] && p != -1) {
24 isAp[u] = true;
25 }
26 }
27 }
28 if (p == -1 && children > 1) {
29 isAp[u] = true;
30 }
31 }
32
33public:
34 vector<int> articulationPoints(int V, vector<vector<int>>& adj) {
35 timer = 0;
36 vector<int> tin(V, -1), low(V, -1);
37 vector<bool> isAp(V, false);
38
39 for (int i = 0; i < V; ++i) {
40 if (tin[i] == -1) {
41 dfs(i, -1, adj, tin, low, isAp);
42 }
43 }
44
45 vector<int> result;
46 for (int i = 0; i < V; ++i) {
47 if (isAp[i]) result.push_back(i);
48 }
49 return result.empty() ? vector<int>{-1} : result;
50 }
51};
52
53int main() {
54 int V = 5;
55 vector<vector<int>> adj(V);
56 vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}};
57 for (auto& e : edges) {
58 adj[e.first].push_back(e.second);
59 adj[e.second].push_back(e.first);
60 }
61 Solution solver;
62 vector<int> aps = solver.articulationPoints(V, adj);
63 for (int u : aps) cout << u << " ";
64 cout << endl;
65 return 0;
66}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Vertex Removal + Component CountingO(V * (V + E))O(V + E)For each vertex v, simulate removing v. Count the number of connected components among the remaining V-1 vertices using BFS. If count > original count, v is an articulation point.Running V separate graph traversals.
2.DFS Tree Cycle CheckingO(V^2)O(V)Construct DFS tree and explicitly verify whether every descendant subtree has an edge leading to an ancestor above u.Subtree-to-ancestor edge validation.
3.Tarjan's Algorithm (Discovery & Low Values)OptimalO(V + E)O(V)Single DFS traversal. Track tin[u] (time when u entered DFS) and low[u] (lowest discovery time reachable via at most one back-edge). Apply the cut-vertex condition on child returns.None; single linear DFS traversal.

Common Pitfalls & Crucial Edge Cases

Reporting duplicate articulation points

A vertex can satisfy low[v] >= tin[u] for multiple children; use a boolean flag array rather than appending directly to a list.

Applying root condition to non-root nodes or vice versa

Leads to false positives for root or false negatives for non-root nodes.

Using low[v] instead of tin[v] when encountering a back-edge

Violates the definition of low-link reachability through at most one back-edge.

Crucial Edge Cases to Validate:

  • Complete graph K_n (n >= 3) — No articulation points exist because every vertex has alternative paths to all others; returns [-1].
  • Star graph (center node 0 connected to 1, 2, ..., n-1) — Center node 0 is the sole articulation point.
  • Line graph (0 - 1 - 2 - ... - n-1) — Every internal vertex (1 to n-2) is an articulation point.
  • Disconnected graph — Traversal must iterate from 0 to V-1 to handle all disconnected components.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State Tarjan's algorithm upfront as the optimal O(V + E) solution.
  2. Clearly delineate the two cases: root (children > 1) vs non-root (low[v] >= tin[u]). Interviewers specifically look for this distinction.
  3. Highlight the difference between an Articulation Point (vertex cut, low[v] >= tin[u]) and a Bridge (edge cut, low[v] > tin[u]).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the articulation point condition for the DFS root different from non-root vertices?

2.Why does the condition low[v] >= tin[u] prove that u is an articulation point for a child v?

3.When encountering a back-edge to a visited neighbor v in DFS, why do we update low[u] = min(low[u], tin[v]) instead of low[v]?

Back to DSA Sheet