Language Selection
Choose your preferred programming language
Showing: Python
Articulation Points (Cut Vertices)
Problem Statement
An articulation point (or cut vertex) in an undirected graph is a vertex whose removal increases the number of connected components. Find all such vertices in a given undirected graph.
Input/Output Specifications
- Input: An undirected graph represented as an adjacency list or edge list
- Output: A list of all articulation points (vertices whose removal disconnects the graph)
Constraints
1 <= n <= 10^4(number of vertices)0 <= edges <= 3 * 10^4- The graph may be disconnected
- No self-loops or multiple edges
Examples
Example 1:
Input: n = 5, edges = [[1,0],[0,2],[2,1],[0,3],[3,4]]
Output: [0, 3]
Explanation:
Graph: 1---0---3---4
| |
2---+
Removing vertex 0 disconnects the graph into {1,2} and {3,4}
Removing vertex 3 disconnects the graph into {0,1,2} and {4}
Example 2:
Input: n = 4, edges = [[0,1],[1,2],[2,3]]
Output: [1, 2]
Explanation:
Graph: 0---1---2---3
Removing vertex 1 disconnects into {0} and {2,3}
Removing vertex 2 disconnects into {0,1} and {3}
Example 3:
Input: n = 7, edges = [[0,1],[1,2],[2,0],[1,3],[1,4],[4,5],[5,6]]
Output: [1, 4, 5]
Explanation:
Graph has a triangle (0,1,2) and a path extending from vertex 1
Solution Approaches
Approach 1: Tarjan’s Algorithm (Optimal)
Algorithm Explanation: Tarjan’s algorithm uses DFS to find articulation points in O(V + E) time using the concept of discovery time and low-link values.
Key concepts:
- Discovery time: When vertex is first visited in DFS
- Low-link value: Lowest discovery time reachable from vertex through back edges
- Articulation point conditions:
- Root of DFS tree with 2+ children
- Non-root vertex u with child v where low[v] >= disc[u]
Implementation:
Python:
def find_articulation_points(n, edges):
"""
Find articulation points using Tarjan's algorithm
Time: O(V + E)
Space: O(V)
"""
# Build adjacency list
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
disc = [0] * n # Discovery times
low = [0] * n # Low-link values
parent = [-1] * n
articulation_points = set()
time = [0] # Use list to modify in nested function
def dfs(u):
children = 0
visited[u] = True
disc[u] = low[u] = time[0]
time[0] += 1
for v in graph[u]:
if not visited[v]:
children += 1
parent[v] = u
dfs(v)
# Update low-link value
low[u] = min(low[u], low[v])
# Articulation point conditions
# 1. Root with 2+ children
if parent[u] == -1 and children > 1:
articulation_points.add(u)
# 2. Non-root with low[v] >= disc[u]
if parent[u] != -1 and low[v] >= disc[u]:
articulation_points.add(u)
elif v != parent[u]: # Back edge
low[u] = min(low[u], disc[v])
# Handle disconnected components
for i in range(n):
if not visited[i]:
dfs(i)
return list(articulation_points)
def find_articulation_points_iterative(n, edges):
"""
Iterative version to avoid recursion depth issues
Time: O(V + E)
Space: O(V)
"""
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
disc = [0] * n
low = [0] * n
parent = [-1] * n
articulation_points = set()
time = 0
for start in range(n):
if visited[start]:
continue
stack = [(start, 0, 0)] # (vertex, neighbor_index, children_count)
children_count = {}
while stack:
u, neighbor_idx, children = stack[-1]
if not visited[u]:
visited[u] = True
disc[u] = low[u] = time
time += 1
children_count[u] = 0
if neighbor_idx < len(graph[u]):
v = graph[u][neighbor_idx]
stack[-1] = (u, neighbor_idx + 1, children)
if not visited[v]:
children_count[u] += 1
parent[v] = u
stack.append((v, 0, 0))
elif v != parent[u]:
low[u] = min(low[u], disc[v])
else:
stack.pop()
if stack:
p = stack[-1][0]
low[p] = min(low[p], low[u])
# Check articulation point conditions
if parent[u] == -1 and children_count[u] > 1:
articulation_points.add(u)
if parent[u] != -1 and low[u] >= disc[parent[u]]:
articulation_points.add(parent[u])
return list(articulation_points)
Java:
class Solution {
/**
* Find articulation points using Tarjan's algorithm
* Time: O(V + E)
* Space: O(V)
*/
public List<Integer> findArticulationPoints(int n, int[][] edges) {
// Build adjacency list
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
int[] disc = new int[n];
int[] low = new int[n];
int[] parent = new int[n];
Arrays.fill(parent, -1);
Set<Integer> articulationPoints = new HashSet<>();
int[] time = {0};
// Handle disconnected components
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, graph, visited, disc, low, parent, articulationPoints, time);
}
}
return new ArrayList<>(articulationPoints);
}
private void dfs(int u, List<List<Integer>> graph, boolean[] visited,
int[] disc, int[] low, int[] parent,
Set<Integer> articulationPoints, int[] time) {
int children = 0;
visited[u] = true;
disc[u] = low[u] = time[0]++;
for (int v : graph.get(u)) {
if (!visited[v]) {
children++;
parent[v] = u;
dfs(v, graph, visited, disc, low, parent, articulationPoints, time);
// Update low-link value
low[u] = Math.min(low[u], low[v]);
// Check articulation point conditions
if (parent[u] == -1 && children > 1) {
articulationPoints.add(u);
}
if (parent[u] != -1 && low[v] >= disc[u]) {
articulationPoints.add(u);
}
} else if (v != parent[u]) {
// Back edge
low[u] = Math.min(low[u], disc[v]);
}
}
}
/**
* Alternative implementation with explicit stack management
*/
public List<Integer> findArticulationPointsIterative(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
int[] disc = new int[n];
int[] low = new int[n];
int[] parent = new int[n];
Arrays.fill(parent, -1);
Set<Integer> articulationPoints = new HashSet<>();
int time = 0;
for (int start = 0; start < n; start++) {
if (visited[start]) continue;
Stack<int[]> stack = new Stack<>(); // [vertex, neighbor_index, children]
stack.push(new int[]{start, 0, 0});
while (!stack.isEmpty()) {
int[] current = stack.peek();
int u = current[0], neighborIdx = current[1], children = current[2];
if (!visited[u]) {
visited[u] = true;
disc[u] = low[u] = time++;
}
if (neighborIdx < graph.get(u).size()) {
int v = graph.get(u).get(neighborIdx);
current[1]++; // Move to next neighbor
if (!visited[v]) {
current[2]++; // Increment children count
parent[v] = u;
stack.push(new int[]{v, 0, 0});
} else if (v != parent[u]) {
low[u] = Math.min(low[u], disc[v]);
}
} else {
stack.pop();
if (!stack.isEmpty()) {
int p = stack.peek()[0];
low[p] = Math.min(low[p], low[u]);
// Check articulation conditions
if (parent[u] == -1 && children > 1) {
articulationPoints.add(u);
}
if (parent[u] != -1 && low[u] >= disc[parent[u]]) {
articulationPoints.add(parent[u]);
}
}
}
}
}
return new ArrayList<>(articulationPoints);
}
}
Go:
// findArticulationPoints - Find articulation points using Tarjan's algorithm
// Time: O(V + E)
// Space: O(V)
func findArticulationPoints(n int, edges [][]int) []int {
// Build adjacency list
graph := make([][]int, n)
for _, edge := range edges {
u, v := edge[0], edge[1]
graph[u] = append(graph[u], v)
graph[v] = append(graph[v], u)
}
visited := make([]bool, n)
disc := make([]int, n)
low := make([]int, n)
parent := make([]int, n)
for i := range parent {
parent[i] = -1
}
articulationPoints := make(map[int]bool)
time := 0
var dfs func(int)
dfs = func(u int) {
children := 0
visited[u] = true
disc[u] = time
low[u] = time
time++
for _, v := range graph[u] {
if !visited[v] {
children++
parent[v] = u
dfs(v)
// Update low-link value
if low[v] < low[u] {
low[u] = low[v]
}
// Check articulation point conditions
if parent[u] == -1 && children > 1 {
articulationPoints[u] = true
}
if parent[u] != -1 && low[v] >= disc[u] {
articulationPoints[u] = true
}
} else if v != parent[u] {
// Back edge
if disc[v] < low[u] {
low[u] = disc[v]
}
}
}
}
// Handle disconnected components
for i := 0; i < n; i++ {
if !visited[i] {
dfs(i)
}
}
result := make([]int, 0, len(articulationPoints))
for point := range articulationPoints {
result = append(result, point)
}
return result
}
// findArticulationPointsIterative - Iterative version
func findArticulationPointsIterative(n int, edges [][]int) []int {
graph := make([][]int, n)
for _, edge := range edges {
u, v := edge[0], edge[1]
graph[u] = append(graph[u], v)
graph[v] = append(graph[v], u)
}
visited := make([]bool, n)
disc := make([]int, n)
low := make([]int, n)
parent := make([]int, n)
for i := range parent {
parent[i] = -1
}
articulationPoints := make(map[int]bool)
time := 0
for start := 0; start < n; start++ {
if visited[start] {
continue
}
// Stack elements: [vertex, neighbor_index, children_count]
stack := [][3]int{{start, 0, 0}}
childrenCount := make(map[int]int)
for len(stack) > 0 {
current := &stack[len(stack)-1]
u, neighborIdx, children := current[0], current[1], current[2]
if !visited[u] {
visited[u] = true
disc[u] = time
low[u] = time
time++
childrenCount[u] = 0
}
if neighborIdx < len(graph[u]) {
v := graph[u][neighborIdx]
current[1]++ // Move to next neighbor
if !visited[v] {
childrenCount[u]++
parent[v] = u
stack = append(stack, [3]int{v, 0, 0})
} else if v != parent[u] {
if disc[v] < low[u] {
low[u] = disc[v]
}
}
} else {
stack = stack[:len(stack)-1] // Pop
if len(stack) > 0 {
p := stack[len(stack)-1][0]
if low[u] < low[p] {
low[p] = low[u]
}
// Check articulation conditions
if parent[u] == -1 && childrenCount[u] > 1 {
articulationPoints[u] = true
}
if parent[u] != -1 && low[u] >= disc[parent[u]] {
articulationPoints[parent[u]] = true
}
}
}
}
}
result := make([]int, 0, len(articulationPoints))
for point := range articulationPoints {
result = append(result, point)
}
return result
}
JavaScript:
/**
* Find articulation points using Tarjan's algorithm
* Time: O(V + E)
* Space: O(V)
*/
function findArticulationPoints(n, edges) {
// Build adjacency list
const graph = Array.from({length: n}, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const visited = new Array(n).fill(false);
const disc = new Array(n).fill(0);
const low = new Array(n).fill(0);
const parent = new Array(n).fill(-1);
const articulationPoints = new Set();
let time = 0;
function dfs(u) {
let children = 0;
visited[u] = true;
disc[u] = low[u] = time++;
for (const v of graph[u]) {
if (!visited[v]) {
children++;
parent[v] = u;
dfs(v);
// Update low-link value
low[u] = Math.min(low[u], low[v]);
// Check articulation point conditions
if (parent[u] === -1 && children > 1) {
articulationPoints.add(u);
}
if (parent[u] !== -1 && low[v] >= disc[u]) {
articulationPoints.add(u);
}
} else if (v !== parent[u]) {
// Back edge
low[u] = Math.min(low[u], disc[v]);
}
}
}
// Handle disconnected components
for (let i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i);
}
}
return Array.from(articulationPoints);
}
/**
* Iterative implementation using explicit stack
*/
function findArticulationPointsIterative(n, edges) {
const graph = Array.from({length: n}, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const visited = new Array(n).fill(false);
const disc = new Array(n).fill(0);
const low = new Array(n).fill(0);
const parent = new Array(n).fill(-1);
const articulationPoints = new Set();
let time = 0;
for (let start = 0; start < n; start++) {
if (visited[start]) continue;
const stack = [[start, 0, 0]]; // [vertex, neighbor_index, children]
const childrenCount = {};
while (stack.length > 0) {
const current = stack[stack.length - 1];
const [u, neighborIdx, children] = current;
if (!visited[u]) {
visited[u] = true;
disc[u] = low[u] = time++;
childrenCount[u] = 0;
}
if (neighborIdx < graph[u].length) {
const v = graph[u][neighborIdx];
current[1]++; // Move to next neighbor
if (!visited[v]) {
childrenCount[u]++;
parent[v] = u;
stack.push([v, 0, 0]);
} else if (v !== parent[u]) {
low[u] = Math.min(low[u], disc[v]);
}
} else {
stack.pop();
if (stack.length > 0) {
const p = stack[stack.length - 1][0];
low[p] = Math.min(low[p], low[u]);
// Check articulation conditions
if (parent[u] === -1 && childrenCount[u] > 1) {
articulationPoints.add(u);
}
if (parent[u] !== -1 && low[u] >= disc[parent[u]]) {
articulationPoints.add(parent[u]);
}
}
}
}
}
return Array.from(articulationPoints);
}
// ES6 arrow function version with modern syntax
const findArticulationPointsES6 = (n, edges) => {
const graph = Array.from({length: n}, () => []);
edges.forEach(([u, v]) => {
graph[u].push(v);
graph[v].push(u);
});
const visited = Array(n).fill(false);
const disc = Array(n).fill(0);
const low = Array(n).fill(0);
const parent = Array(n).fill(-1);
const articulationPoints = new Set();
let time = 0;
const dfs = (u) => {
let children = 0;
visited[u] = true;
disc[u] = low[u] = time++;
graph[u].forEach(v => {
if (!visited[v]) {
children++;
parent[v] = u;
dfs(v);
low[u] = Math.min(low[u], low[v]);
if ((parent[u] === -1 && children > 1) ||
(parent[u] !== -1 && low[v] >= disc[u])) {
articulationPoints.add(u);
}
} else if (v !== parent[u]) {
low[u] = Math.min(low[u], disc[v]);
}
});
};
Array.from({length: n}, (_, i) => i)
.filter(i => !visited[i])
.forEach(dfs);
return [...articulationPoints];
};
C#:
public class Solution {
/// <summary>
/// Find articulation points using Tarjan's algorithm
/// Time: O(V + E)
/// Space: O(V)
/// </summary>
public IList<int> FindArticulationPoints(int n, int[][] edges) {
// Build adjacency list
var graph = new List<List<int>>();
for (int i = 0; i < n; i++) {
graph.Add(new List<int>());
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
bool[] visited = new bool[n];
int[] disc = new int[n];
int[] low = new int[n];
int[] parent = new int[n];
Array.Fill(parent, -1);
var articulationPoints = new HashSet<int>();
int time = 0;
// Handle disconnected components
for (int i = 0; i < n; i++) {
if (!visited[i]) {
Dfs(i, graph, visited, disc, low, parent, articulationPoints, ref time);
}
}
return articulationPoints.ToList();
}
private void Dfs(int u, List<List<int>> graph, bool[] visited,
int[] disc, int[] low, int[] parent,
HashSet<int> articulationPoints, ref int time) {
int children = 0;
visited[u] = true;
disc[u] = low[u] = time++;
foreach (int v in graph[u]) {
if (!visited[v]) {
children++;
parent[v] = u;
Dfs(v, graph, visited, disc, low, parent, articulationPoints, ref time);
// Update low-link value
low[u] = Math.Min(low[u], low[v]);
// Check articulation point conditions
if (parent[u] == -1 && children > 1) {
articulationPoints.Add(u);
}
if (parent[u] != -1 && low[v] >= disc[u]) {
articulationPoints.Add(u);
}
} else if (v != parent[u]) {
// Back edge
low[u] = Math.Min(low[u], disc[v]);
}
}
}
/// <summary>
/// LINQ-enhanced version with functional approach
/// </summary>
public IList<int> FindArticulationPointsLinq(int n, int[][] edges) {
var graph = Enumerable.Range(0, n)
.ToDictionary(i => i, i => new List<int>());
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
var visited = new bool[n];
var disc = new int[n];
var low = new int[n];
var parent = Enumerable.Repeat(-1, n).ToArray();
var articulationPoints = new HashSet<int>();
var time = 0;
var unvisitedComponents = Enumerable.Range(0, n)
.Where(i => !visited[i]);
foreach (int start in unvisitedComponents) {
DfsLinq(start, graph, visited, disc, low, parent, articulationPoints, ref time);
}
return articulationPoints.OrderBy(x => x).ToList();
}
private void DfsLinq(int u, Dictionary<int, List<int>> graph, bool[] visited,
int[] disc, int[] low, int[] parent,
HashSet<int> articulationPoints, ref int time) {
var children = 0;
visited[u] = true;
disc[u] = low[u] = time++;
foreach (var v in graph[u]) {
if (!visited[v]) {
children++;
parent[v] = u;
DfsLinq(v, graph, visited, disc, low, parent, articulationPoints, ref time);
low[u] = Math.Min(low[u], low[v]);
if ((parent[u] == -1 && children > 1) ||
(parent[u] != -1 && low[v] >= disc[u])) {
articulationPoints.Add(u);
}
} else if (v != parent[u]) {
low[u] = Math.Min(low[u], disc[v]);
}
}
}
}
Complexity Analysis:
- Time Complexity: O(V + E) - Each vertex and edge visited once
- Space Complexity: O(V) - For arrays and recursion stack
Trade-offs:
- Optimal time complexity for this problem
- Single pass algorithm
- Handles disconnected graphs
- Requires understanding of DFS and graph theory concepts
Approach 2: Naive Approach (Remove Each Vertex)
Algorithm Explanation: For each vertex, temporarily remove it and check if the graph becomes disconnected.
Implementation:
Python:
def find_articulation_points_naive(n, edges):
"""
Naive approach - remove each vertex and check connectivity
Time: O(V * (V + E))
Space: O(V + E)
"""
# Build adjacency list
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
def count_components(excluded_vertex):
visited = [False] * n
components = 0
for i in range(n):
if i == excluded_vertex or visited[i]:
continue
# BFS/DFS to mark connected component
stack = [i]
visited[i] = True
components += 1
while stack:
curr = stack.pop()
for neighbor in graph[curr]:
if neighbor != excluded_vertex and not visited[neighbor]:
visited[neighbor] = True
stack.append(neighbor)
return components
# Count components in original graph
original_components = count_components(-1) # No vertex excluded
articulation_points = []
# Check each vertex
for vertex in range(n):
if count_components(vertex) > original_components:
articulation_points.append(vertex)
return articulation_points
Complexity Analysis:
- Time Complexity: O(V * (V + E)) - Check each vertex, run DFS for each
- Space Complexity: O(V + E) - For graph representation and visited array
Trade-offs:
- Simple to understand and implement
- Much slower than Tarjan’s algorithm
- Useful for educational purposes or small graphs
- Good for verifying correctness of optimal solution
Key Insights
- Tarjan’s Algorithm: Uses DFS tree properties and low-link values
- Two conditions for articulation points:
- Root of DFS tree with multiple children
- Non-root vertex where removal disconnects subtree
- Low-link values: Key insight for efficient detection
- Single DFS pass: No need to actually remove vertices
- Back edges: Help maintain connectivity through low-link updates
Edge Cases
- Empty graph: No vertices → No articulation points
- Single vertex: One vertex → No articulation points
- Two vertices: Connected → Both are articulation points
- Disconnected graph: Each component analyzed separately
- Complete graph: No articulation points (highly connected)
- Linear path: All internal vertices are articulation points
- Cycle: No articulation points
How Solutions Handle Edge Cases:
- Empty/single vertex: Loop handles naturally
- Two vertices: Detected as articulation points
- Disconnected: Algorithm processes each component
- Complete graphs: No vertex satisfies articulation conditions
- Linear paths: Internal vertices detected correctly
Test Cases
def test_articulation_points():
# Example 1: Basic case
edges1 = [[1,0],[0,2],[2,1],[0,3],[3,4]]
result1 = find_articulation_points(5, edges1)
assert set(result1) == {0, 3}
# Example 2: Linear path
edges2 = [[0,1],[1,2],[2,3]]
result2 = find_articulation_points(4, edges2)
assert set(result2) == {1, 2}
# Example 3: Cycle (no articulation points)
edges3 = [[0,1],[1,2],[2,0]]
result3 = find_articulation_points(3, edges3)
assert len(result3) == 0
# Example 4: Disconnected graph
edges4 = [[0,1],[2,3]]
result4 = find_articulation_points(4, edges4)
assert len(result4) == 0
# Example 5: Star graph
edges5 = [[0,1],[0,2],[0,3],[0,4]]
result5 = find_articulation_points(5, edges5)
assert result5 == [0]
# Example 6: Bridge with cycles
edges6 = [[0,1],[1,2],[2,0],[1,3],[3,4],[4,5],[5,3]]
result6 = find_articulation_points(6, edges6)
assert 1 in result6 and 3 in result6
print("All tests passed!")
test_articulation_points()
Follow-up Questions
- Find bridges: How would you modify the algorithm to find bridges (critical edges)?
- Dynamic articulation points: How would you handle edge insertions/deletions?
- Block-cut tree: How would you construct a block-cut tree representation?
- 2-connected components: How would you find all biconnected components?
- Online algorithm: How would you handle real-time queries?
Common Mistakes
Incorrect back edge handling: Not properly updating low-link values
- Problem: Missing articulation points in cycles
- Solution: Update low[u] = min(low[u], disc[v]) for back edges
Wrong root condition: Checking children count incorrectly
- Problem: False positives for DFS tree root
- Solution: Root is articulation point only if it has 2+ children
Parent edge confusion: Treating parent edge as back edge
- Problem: Incorrect low-link value updates
- Solution: Explicitly check v != parent[u]
Time initialization: Not resetting time for disconnected components
- Problem: Incorrect discovery times
- Solution: Use global time counter across all DFS calls
Interview Tips
- Start with concept: Explain what articulation points are before coding
- Draw examples: Visualize small graphs to demonstrate the concept
- Mention applications: Network reliability, social network analysis
- Discuss alternatives: Compare with naive O(V*(V+E)) approach
- Handle edge cases: Show awareness of disconnected graphs and special cases
Concept Explanations
DFS Tree Properties: Tarjan’s algorithm leverages the structure of DFS trees where tree edges and back edges have specific properties that help identify critical vertices.
Low-Link Values: The lowest discovery time reachable from a vertex through its subtree, used to determine if removing a vertex would disconnect the graph.
When to Apply: Use for network reliability analysis, finding critical nodes in infrastructure, social network analysis, and as a building block for more complex graph algorithms like finding biconnected components.