Articulation Points (Cut Vertices)
Description
You are given an undirected graph with V vertices (numbered 0 to V - 1) and a list of edges. Your task is to find all articulation points (also called cut vertices) in the graph.
An articulation point is a vertex whose removal — along with all edges connected to it — increases the number of connected components in the graph. In other words, removing an articulation point splits a previously connected part of the graph into two or more separate pieces.
Return all articulation points in sorted order. If no articulation point exists, return [-1].
Note: The graph may contain more than one connected component, and there might be self-loops present.
Examples
Example 1
Input: V = 5, edges = [[0,1],[1,4],[4,3],[4,2],[2,3]]
Output: [1, 4]
Explanation: Consider what happens when each node is removed:
- Remove node 0: The remaining nodes {1, 2, 3, 4} are still connected through edges 1-4, 4-3, 4-2, 2-3. No disconnection.
- Remove node 1: Node 0 becomes isolated (its only connection was to node 1). Nodes {2, 3, 4} remain connected. The graph splits into {0} and {2, 3, 4} — two components. Node 1 is an articulation point.
- Remove node 2: Nodes {0, 1, 3, 4} are still connected via 0-1, 1-4, 4-3. No disconnection.
- Remove node 3: Nodes {0, 1, 2, 4} are still connected via 0-1, 1-4, 4-2. No disconnection.
- Remove node 4: Node 0 connects to node 1, but nodes 2 and 3 only connected to node 4 (and each other). The graph splits into {0, 1} and {2, 3} — two components. Node 4 is an articulation point.
Articulation points: [1, 4].
Example 2
Input: V = 4, edges = [[0,1],[0,2]]
Output: [0]
Explanation: Node 0 is connected to both node 1 and node 2, but nodes 1 and 2 have no edge between them. Node 3 is already isolated. Removing node 0 disconnects node 1 from node 2, increasing the number of components from 2 (the component {0,1,2} and the isolated {3}) to 3 ({1}, {2}, {3}). Node 0 is the only articulation point.
Example 3
Input: V = 3, edges = [[0,1],[1,2],[2,0]]
Output: [-1]
Explanation: All three nodes form a cycle (triangle). Removing any single node leaves the other two still connected by a direct edge. No articulation points exist.
Constraints
- 1 ≤ V ≤ 10^5
- 0 ≤ E ≤ 10^5
- 0 ≤ edges[i][0], edges[i][1] ≤ V - 1
- The graph is undirected.
- There might be self-loops present in the graph.
- The graph may contain more than one connected component.
Editorial
Brute Force
Intuition
The most direct way to find articulation points is to test each vertex individually. For every vertex in the graph, pretend to remove it (along with all its edges), then check if the remaining graph has more connected components than before.
Imagine a group of friends connected by phone calls. To find out who the critical "connectors" are, you could silence each person one at a time and see if any pair of remaining friends can no longer reach each other through the phone chain. If silencing person X breaks the chain, then X is a critical connector — an articulation point.
To check connectivity after removing a vertex, we mark the removed vertex as already visited (so DFS skips it), then count how many separate DFS traversals are needed to visit all of its neighbors. If we need more than one DFS call, that vertex was holding together multiple groups.
Step-by-Step Explanation
Let's trace through with V = 5, edges = [[0,1],[1,4],[4,3],[4,2],[2,3]]:
Step 1: Build adjacency list. Node 0: {1}. Node 1: {0, 4}. Node 2: {3, 4}. Node 3: {2, 4}. Node 4: {1, 2, 3}.
Step 2: Test node 0. Mark node 0 as visited (pretend removed). Node 0's neighbors: {1}. DFS from 1 reaches {1, 4, 2, 3}. Only 1 DFS call needed. Comp = 1. Node 0 is NOT an articulation point.
Step 3: Test node 1. Mark node 1 as visited. Node 1's neighbors: {0, 4}. DFS from 0: reaches only {0} (node 0 has no other connections besides node 1 which is removed). DFS from 4: reaches {4, 2, 3}. Two DFS calls needed. Comp = 2. Node 1 IS an articulation point.
Step 4: Test node 2. Mark node 2 as visited. Node 2's neighbors: {3, 4}. DFS from 3: reaches {3, 4, 1, 0} (via 3→4→1→0). Only 1 DFS call covers all neighbors. Comp = 1. Node 2 is NOT an articulation point.
Step 5: Test node 3. Mark node 3 as visited. Node 3's neighbors: {2, 4}. DFS from 2: reaches {2, 4, 1, 0}. Only 1 DFS call needed. Comp = 1. Node 3 is NOT an articulation point.
Step 6: Test node 4. Mark node 4 as visited. Node 4's neighbors: {1, 2, 3}. DFS from 1: reaches {1, 0}. DFS from 2: reaches {2, 3}. Two DFS calls needed. Comp = 2. Node 4 IS an articulation point.
Step 7: Return sorted result: [1, 4].
Brute Force — Testing Each Vertex for Articulation Property — Watch as we remove each vertex one at a time and check if its neighbors remain connected. Nodes 1 and 4 cause disconnection when removed.
Algorithm
- Build an adjacency list from the edges.
- For each vertex
ufrom 0 to V-1:
a. Mark vertexuas visited (pretend it's removed).
b. For each unvisited neighbor ofu, start a DFS. Count the number of separate DFS calls needed (comp).
c. Ifcomp > 1, vertexuis an articulation point — add it to the result.
d. Reset visited array. - Sort the result and return it. If empty, return [-1].
Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) {
visited[node] = true;
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
dfs(neighbor, adj, visited);
}
}
}
vector<int> articulationPoints(int V, vector<vector<int>>& edges) {
// Build adjacency list
vector<vector<int>> adj(V);
for (auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
vector<int> result;
for (int u = 0; u < V; u++) {
// Pretend node u is removed
vector<bool> visited(V, false);
visited[u] = true; // skip this node
int comp = 0;
for (int neighbor : adj[u]) {
if (!visited[neighbor]) {
dfs(neighbor, adj, visited);
comp++;
}
}
if (comp > 1) {
result.push_back(u);
}
}
if (result.empty()) return {-1};
sort(result.begin(), result.end());
return result;
}
};import sys
from collections import defaultdict
sys.setrecursionlimit(200000)
class Solution:
def articulationPoints(self, V: int, edges: list[list[int]]) -> list[int]:
# Build adjacency list
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
def dfs(node, visited):
visited[node] = True
for neighbor in adj[node]:
if not visited[neighbor]:
dfs(neighbor, visited)
result = []
for u in range(V):
# Pretend node u is removed
visited = [False] * V
visited[u] = True # skip this node
comp = 0
for neighbor in adj[u]:
if not visited[neighbor]:
dfs(neighbor, visited)
comp += 1
if comp > 1:
result.append(u)
return sorted(result) if result else [-1]import java.util.*;
class Solution {
private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, adj, visited);
}
}
}
public List<Integer> articulationPoints(int V, List<int[]> edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
List<Integer> result = new ArrayList<>();
for (int u = 0; u < V; u++) {
boolean[] visited = new boolean[V];
visited[u] = true; // pretend removed
int comp = 0;
for (int neighbor : adj.get(u)) {
if (!visited[neighbor]) {
dfs(neighbor, adj, visited);
comp++;
}
}
if (comp > 1) {
result.add(u);
}
}
if (result.isEmpty()) {
result.add(-1);
}
Collections.sort(result);
return result;
}
}Complexity Analysis
Time Complexity: O(V × (V + E))
For each of the V vertices, we pretend to remove it and run DFS over the remaining graph. Each DFS costs O(V + E). Total: V × O(V + E) = O(V × (V + E)).
With V up to 10^5 and E up to 10^5, this results in roughly 10^5 × 2 × 10^5 = 2 × 10^10 operations — far too slow for competitive programming time limits.
Space Complexity: O(V + E)
The adjacency list takes O(V + E), and the visited array takes O(V) for each DFS run. The DFS recursion stack can be up to O(V) deep.
Why This Approach Is Not Efficient
The brute force approach tests each vertex independently by removing it and running a full DFS traversal. With V up to 10^5 vertices and each traversal costing O(V + E), the total time is O(V × (V + E)) ≈ O(V² + VE). For maximum constraints, this is approximately 10^10 operations — well beyond the typical 1-second time limit.
The root cause of inefficiency is that each vertex removal is treated as a completely independent problem. We rebuild the visited state from scratch every time and learn nothing from one test that could help the next.
Key insight: Instead of physically removing each vertex, we can analyze the DFS tree structure in a single pass. A vertex u is an articulation point if and only if:
- Root case:
uis the DFS root and has two or more children in the DFS tree (removing the root disconnects its children since they were only reachable via the root). - Non-root case:
uhas a childvin the DFS tree such that no vertex in the subtree rooted atvhas a back-edge to an ancestor ofu. This is captured by the conditionlow[v] ≥ disc[u]— meaningv's subtree cannot "escape" aboveuthrough any back-edge.
This is Tarjan's Algorithm, which solves the problem in a single DFS pass: O(V + E).
Optimal Approach - Tarjan's Algorithm
Intuition
Tarjan's algorithm for finding articulation points builds on a clever observation about DFS tree structure. When we run DFS on a graph, we create a tree (the DFS tree) where some edges go "down" to new nodes (tree edges) and some go "back" to already-visited ancestors (back-edges). Back-edges create cycles, and cycles are the reason some vertices are NOT articulation points — they provide alternative paths.
Think of a city with a road network. Some roads form the main route (DFS tree edges), while others are shortcuts back to earlier intersections (back-edges). An intersection is critical (an articulation point) only if there's NO shortcut that bypasses it. If every road below an intersection eventually has a shortcut back above it, then that intersection isn't critical.
To formalize this, we track two values for each vertex:
- disc[u] (discovery time): The order in which DFS first visits vertex
u. - low[u]: The smallest discovery time reachable from
u's subtree through tree edges and at most one back-edge.
The two rules for identifying articulation points are:
- Root rule: If
uis the DFS root and has ≥ 2 children in the DFS tree,uis an articulation point. Rationale: the root's children are in separate subtrees; they only connect through the root. - Non-root rule: If
uis not the root and has a childvwherelow[v] ≥ disc[u], thenuis an articulation point. Rationale:v's entire subtree cannot reach any ancestor ofu— no back-edge provides an escape route pastu.
Note the subtle difference from bridges: bridges use low[v] > disc[u] (strict), while articulation points use low[v] ≥ disc[u] (non-strict). This is because even if the back-edge reaches u itself (low[v] == disc[u]), removing u would still disconnect v's subtree — the back-edge goes TO the very node being removed.
Step-by-Step Explanation
Let's trace through with V = 5, edges = [[0,1],[1,4],[4,3],[4,2],[2,3]]:
Step 1: Initialize timer = 0. All disc[] and low[] start as -1. Start DFS from node 0 (which becomes the root).
Step 2: Visit node 0. Set disc[0] = low[0] = 0. Timer becomes 1. children_count = 0. Explore neighbor 1.
Step 3: Visit node 1 (parent = 0). Set disc[1] = low[1] = 1. Timer becomes 2. Explore neighbor 0 — skip, parent. Explore neighbor 4.
Step 4: Visit node 4 (parent = 1). Set disc[4] = low[4] = 2. Timer becomes 3. Explore neighbor 1 — skip, parent. Explore neighbor 3.
Step 5: Visit node 3 (parent = 4). Set disc[3] = low[3] = 3. Timer becomes 4. Explore neighbor 2.
Step 6: Visit node 2 (parent = 3). Set disc[2] = low[2] = 4. Timer becomes 5. Explore neighbor 3 — skip, parent. Explore neighbor 4 — already visited, NOT parent. Back-edge! Update low[2] = min(4, disc[4]) = min(4, 2) = 2.
Step 7: Return to node 3 from child 2. Update low[3] = min(low[3], low[2]) = min(3, 2) = 2. Check: low[2] = 2 ≥ disc[3] = 3? NO (2 < 3). Node 3 is NOT an articulation point. Explore neighbor 4 — already visited, NOT parent. Back-edge! Update low[3] = min(2, disc[4]) = min(2, 2) = 2.
Step 8: Return to node 4 from child 3. Update low[4] = min(low[4], low[3]) = min(2, 2) = 2. Check: low[3] = 2 ≥ disc[4] = 2? YES! Node 4 IS an articulation point. Explore neighbor 2 — already visited, NOT parent. Back-edge! Update low[4] = min(2, disc[2]) = min(2, 4) = 2 (no change).
Step 9: Return to node 1 from child 4. Update low[1] = min(low[1], low[4]) = min(1, 2) = 1. Check: low[4] = 2 ≥ disc[1] = 1? YES! Node 1 IS an articulation point.
Step 10: Return to node 0 from child 1. Update low[0] = min(low[0], low[1]) = min(0, 1) = 0. Root check: node 0 has only 1 child (node 1) in DFS tree. Since children < 2, node 0 is NOT an articulation point.
Step 11: DFS complete. Result: [1, 4].
Final values: disc = [0, 1, 4, 3, 2], low = [0, 1, 2, 2, 2]. Articulation points: nodes 1 and 4.
Tarjan's Algorithm — Finding Articulation Points via DFS Discovery and Low Values — Watch how DFS assigns discovery times and computes low values. When low[v] ≥ disc[u] for non-root u, or root has ≥ 2 children, u is an articulation point.
Algorithm
- Build an adjacency list from the edges.
- Initialize
disc[],low[]arrays with -1, avisited[]array, and a global timer = 0. - For each unvisited node, start a DFS.
- In DFS for node
uwith parentp:
a. Setdisc[u] = low[u] = timer++. Mark visited.
b. Initializechildren_count = 0.
c. For each neighborvofu:- If
v == p: skip (parent edge). - If
vis unvisited: recurse DFS(v, u). Incrementchildren_count. Updatelow[u] = min(low[u], low[v]). Ifp ≠ -1(non-root) andlow[v] ≥ disc[u]: markuas articulation point. - If
vis already visited: back-edge. Updatelow[u] = min(low[u], disc[v]).
d. After processing all neighbors: ifp == -1(root) andchildren_count ≥ 2: markuas articulation point.
- If
- Collect all marked articulation points, sort, and return. If none, return [-1].
Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int timer = 0;
void dfs(int u, int parent, vector<vector<int>>& adj,
vector<int>& disc, vector<int>& low,
vector<bool>& visited, vector<bool>& isAP) {
visited[u] = true;
disc[u] = low[u] = timer++;
int children = 0;
for (int v : adj[u]) {
if (v == parent) {
parent = -1; // skip parent only once
continue;
}
if (!visited[v]) {
children++;
dfs(v, u, adj, disc, low, visited, isAP);
low[u] = min(low[u], low[v]);
// Non-root articulation point condition
if (parent != -1 && low[v] >= disc[u]) {
isAP[u] = true;
}
} else {
// Back edge
low[u] = min(low[u], disc[v]);
}
}
// Root articulation point condition
// Note: we need to check original parent, not modified one
// Using disc[u] == 0 for root check if started from 0
}
vector<int> articulationPoints(int V, vector<vector<int>>& edges) {
vector<vector<int>> adj(V);
for (auto& edge : edges) {
if (edge[0] == edge[1]) continue; // skip self-loops
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
vector<int> disc(V, -1), low(V, -1);
vector<bool> visited(V, false), isAP(V, false);
timer = 0;
for (int i = 0; i < V; i++) {
if (!visited[i]) {
// Custom DFS for root handling
visited[i] = true;
disc[i] = low[i] = timer++;
int rootChildren = 0;
for (int v : adj[i]) {
if (!visited[v]) {
rootChildren++;
dfs(v, i, adj, disc, low, visited, isAP);
low[i] = min(low[i], low[v]);
if (low[v] >= disc[i] && rootChildren > 1) {
isAP[i] = true;
}
} else {
low[i] = min(low[i], disc[v]);
}
}
if (rootChildren >= 2) {
isAP[i] = true;
}
}
}
vector<int> result;
for (int i = 0; i < V; i++) {
if (isAP[i]) result.push_back(i);
}
if (result.empty()) return {-1};
return result;
}
};import sys
from collections import defaultdict
sys.setrecursionlimit(200000)
class Solution:
def articulationPoints(self, V: int, edges: list[list[int]]) -> list[int]:
adj = defaultdict(list)
for u, v in edges:
if u == v: # skip self-loops
continue
adj[u].append(v)
adj[v].append(u)
disc = [-1] * V
low = [-1] * V
visited = [False] * V
is_ap = [False] * V
timer = [0]
def dfs(u: int, parent: int) -> None:
visited[u] = True
disc[u] = low[u] = timer[0]
timer[0] += 1
children = 0
for v in adj[u]:
if v == parent:
parent = -1 # skip parent only once
continue
if not visited[v]:
children += 1
dfs(v, u)
low[u] = min(low[u], low[v])
# Non-root: articulation point check
if parent != -1 and low[v] >= disc[u]:
is_ap[u] = True
else:
# Back edge
low[u] = min(low[u], disc[v])
# Root: articulation point if ≥ 2 children
# We check original parent via disc comparison
for i in range(V):
if not visited[i]:
# Handle root specially
visited[i] = True
disc[i] = low[i] = timer[0]
timer[0] += 1
root_children = 0
for v in adj[i]:
if not visited[v]:
root_children += 1
dfs(v, i)
low[i] = min(low[i], low[v])
else:
low[i] = min(low[i], disc[v])
if root_children >= 2:
is_ap[i] = True
result = [i for i in range(V) if is_ap[i]]
return result if result else [-1]import java.util.*;
class Solution {
private int timer = 0;
private void dfs(int u, int parent, List<List<Integer>> adj,
int[] disc, int[] low, boolean[] visited, boolean[] isAP) {
visited[u] = true;
disc[u] = low[u] = timer++;
int children = 0;
for (int v : adj.get(u)) {
if (v == parent) {
parent = -1; // skip parent only once
continue;
}
if (!visited[v]) {
children++;
dfs(v, u, adj, disc, low, visited, isAP);
low[u] = Math.min(low[u], low[v]);
// Non-root articulation point
if (parent != -1 && low[v] >= disc[u]) {
isAP[u] = true;
}
} else {
// Back edge
low[u] = Math.min(low[u], disc[v]);
}
}
}
public List<Integer> articulationPoints(int V, List<int[]> edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
for (int[] edge : edges) {
if (edge[0] == edge[1]) continue; // skip self-loops
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
int[] disc = new int[V];
int[] low = new int[V];
boolean[] visited = new boolean[V];
boolean[] isAP = new boolean[V];
Arrays.fill(disc, -1);
Arrays.fill(low, -1);
timer = 0;
for (int i = 0; i < V; i++) {
if (!visited[i]) {
// Handle root specially
visited[i] = true;
disc[i] = low[i] = timer++;
int rootChildren = 0;
for (int v : adj.get(i)) {
if (!visited[v]) {
rootChildren++;
dfs(v, i, adj, disc, low, visited, isAP);
low[i] = Math.min(low[i], low[v]);
} else {
low[i] = Math.min(low[i], disc[v]);
}
}
if (rootChildren >= 2) {
isAP[i] = true;
}
}
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < V; i++) {
if (isAP[i]) result.add(i);
}
if (result.isEmpty()) result.add(-1);
return result;
}
}Complexity Analysis
Time Complexity: O(V + E)
We perform a single DFS traversal of the entire graph. Each vertex is visited exactly once (O(V)), and each edge is examined exactly twice — once from each endpoint (O(E)). The disc/low computations, comparison checks, and articulation point marking at each step are all O(1) operations. Total: O(V + E).
For maximum constraints (V = 10^5, E = 10^5), this is approximately 2 × 10^5 operations — an enormous improvement over the brute force's 10^10.
Space Complexity: O(V + E)
We store the adjacency list (O(V + E)), the disc[], low[], visited[], and isAP[] arrays (O(V) each), and the DFS recursion stack (O(V) in the worst case for a chain graph). Total: O(V + E).