Articulation Points in a Graph — Problem & Solution
Articulation Points in a Graph solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Articulation Points in a Graph is a hard coding problem on depth-first search and graph, asked in Amazon, Microsoft and Samsung interviews.
- Difficulty: Hard
- Topics: Depth-First Search, Graph
- Asked at: Amazon, Microsoft, Samsung
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an undirected graph with n vertices numbered 0 to n - 1; each edges[i] = [u, v] connects u and v. The graph need not be connected.
A vertex is an articulation point (a cut vertex) if deleting it, together with its edges, increases the number of connected components of the graph.
Return every articulation point in ascending order. If the graph has none, return [-1].
Example 1
Input: n = 5, edges = [[0,1],[1,4],[4,3],[4,2],[2,3]]
Output: [1,4]
Explanation: Removing 1 cuts 0 off; removing 4 separates {0, 1} from {2, 3}. The triangle 2–3–4 survives losing 2 or 3.
Example 2
Input: n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
Output: [-1]
Explanation: On a cycle every vertex has a way around, so no single deletion disconnects anything.
Example 3
Input: n = 3, edges = [[0,1],[1,2]]
Output: [1]
Constraints
1 <= n <= 10^40 <= edges.length <= 10^4edges[i].length == 20 <= u, v < n, u != vthere are no repeated edges
Hints for Articulation Points in a Graph
Hint 1
Run a DFS and record each vertex's discovery time
disc[u]. Edges that go back to an ancestor are the only way a subtree can bypass its parent.Hint 2
Let
low[u]be the earliest discovery time reachable fromu's subtree using tree edges down and at most one back edge up.Hint 3
A non-root
uis a cut vertex if some childvhaslow[v] >= disc[u]. The DFS root is a cut vertex exactly when it has two or more DFS children.
How to solve Articulation Points in a Graph
Tarjan's low-link technique finds every cut vertex in one DFS. A child subtree that cannot climb above u without passing through u gets disconnected when u is removed.
Approach
- Build the adjacency list. Set
disc[u] = -1for allu. - For each undiscovered vertex, start a DFS as a root with parent
-1. - In
dfs(u, parent): setdisc[u] = low[u] = timer++. For each neighbourv: if undiscovered, recurse, count a child, setlow[u] = min(low[u], low[v]), and markuifparent != -1andlow[v] >= disc[u]; else ifv != parent, setlow[u] = min(low[u], disc[v]). - After the loop, mark a root
uif it has more than one DFS child. - Collect marked vertices in ascending order, or return
[-1]if there are none.
Why it works
In an undirected DFS every non-tree edge joins a vertex to one of its ancestors. If child v has low[v] >= disc[u], no vertex in v's subtree has an edge to a proper ancestor of u, so every path from that subtree to the rest of the graph passes through u — deleting u disconnects it. Conversely if every child can reach above u, all children stay attached to u's parent. A root has no ancestor, so it separates its subtrees exactly when it has more than one.
Complexity
- Time —
O(n + E) - Space —
O(n + E)
Pitfalls
- The root needs its own rule:
low[v] >= disc[root]holds for every child of the root. - Update
low[u]from a back edge withdisc[v], notlow[v]. - A vertex can be found as a cut vertex through several children — mark it once, not once per child.
- Restart the DFS from every undiscovered vertex: the graph may be disconnected.
Reference solution
Python
import sys
from typing import List
def articulationPoints(n: int, edges: List[List[int]]) -> List[int]:
sys.setrecursionlimit(max(1000, 4 * n + 100))
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
disc = [-1] * n
low = [0] * n
cut = [False] * n
timer = [0]
def dfs(u, parent):
disc[u] = low[u] = timer[0]
timer[0] += 1
children = 0
for v in adj[u]:
if disc[v] == -1:
children += 1
dfs(v, u)
low[u] = min(low[u], low[v])
if parent != -1 and low[v] >= disc[u]:
cut[u] = True
elif v != parent:
low[u] = min(low[u], disc[v])
if parent == -1 and children > 1:
cut[u] = True
for u in range(n):
if disc[u] == -1:
dfs(u, -1)
res = [u for u in range(n) if cut[u]]
return res if res else [-1]Java
static int apTimer;
public static int[] articulationPoints(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
int[] disc = new int[n], low = new int[n];
boolean[] cut = new boolean[n];
Arrays.fill(disc, -1);
apTimer = 0;
for (int u = 0; u < n; u++) if (disc[u] == -1) apDfs(adj, u, -1, disc, low, cut);
List<Integer> res = new ArrayList<>();
for (int u = 0; u < n; u++) if (cut[u]) res.add(u);
if (res.isEmpty()) return new int[]{-1};
int[] out = new int[res.size()];
for (int i = 0; i < out.length; i++) out[i] = res.get(i);
return out;
}
static void apDfs(List<List<Integer>> adj, int u, int parent, int[] disc, int[] low, boolean[] cut) {
disc[u] = low[u] = apTimer++;
int children = 0;
for (int v : adj.get(u)) {
if (disc[v] == -1) {
children++;
apDfs(adj, v, u, disc, low, cut);
low[u] = Math.min(low[u], low[v]);
if (parent != -1 && low[v] >= disc[u]) cut[u] = true;
} else if (v != parent) {
low[u] = Math.min(low[u], disc[v]);
}
}
if (parent == -1 && children > 1) cut[u] = true;
}C++
static void apDfs(vector<vector<int>>& adj, int u, int parent, vector<int>& disc, vector<int>& low, vector<bool>& cut, int& timer) {
disc[u] = low[u] = timer++;
int children = 0;
for (int v : adj[u]) {
if (disc[v] == -1) {
children++;
apDfs(adj, v, u, disc, low, cut, timer);
low[u] = min(low[u], low[v]);
if (parent != -1 && low[v] >= disc[u]) cut[u] = true;
} else if (v != parent) {
low[u] = min(low[u], disc[v]);
}
}
if (parent == -1 && children > 1) cut[u] = true;
}
vector<int> articulationPoints(int n, vector<vector<int>>& edges) {
vector<vector<int>> adj(n);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
vector<int> disc(n, -1), low(n, 0);
vector<bool> cut(n, false);
int timer = 0;
for (int u = 0; u < n; u++) if (disc[u] == -1) apDfs(adj, u, -1, disc, low, cut, timer);
vector<int> res;
for (int u = 0; u < n; u++) if (cut[u]) res.push_back(u);
if (res.empty()) res.push_back(-1);
return res;
}JavaScript
var articulationPoints = function(n, edges) {
var adj = [], disc = [], low = [], cut = [];
for (var i = 0; i < n; i++) { adj.push([]); disc.push(-1); low.push(0); cut.push(false); }
for (var k = 0; k < edges.length; k++) { adj[edges[k][0]].push(edges[k][1]); adj[edges[k][1]].push(edges[k][0]); }
var timer = 0;
var dfs = function(u, parent) {
disc[u] = low[u] = timer++;
var children = 0;
for (var j = 0; j < adj[u].length; j++) {
var v = adj[u][j];
if (disc[v] === -1) {
children++;
dfs(v, u);
low[u] = Math.min(low[u], low[v]);
if (parent !== -1 && low[v] >= disc[u]) cut[u] = true;
} else if (v !== parent) {
low[u] = Math.min(low[u], disc[v]);
}
}
if (parent === -1 && children > 1) cut[u] = true;
};
for (var u = 0; u < n; u++) if (disc[u] === -1) dfs(u, -1);
var res = [];
for (var x = 0; x < n; x++) if (cut[x]) res.push(x);
return res.length ? res : [-1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Graph Data Structure