Articulation Points in Graphs

Problem and examples

In an undirected connected graph, an articulation point (or cut vertex) is a node that, when removed (along with its edges), increases the number of connected components in the graph.

Problem: Given an undirected graph with V vertices and an adjacency list adj, find all articulation points.

Indexing is 0-based, i.e., nodes are numbered from 0 to V-1.
There may be self-loops and multiple edges, but you should still identify articulation points based on connectivity.

Graph (Adjacency List)	Articulation Points	Description
{0:[1,2], 1:[0,2], 2:[0,1,3], 3:[2,4,5], 4:[3], 5:[3]}	[2,3]	Removing node 2 or 3 disconnects parts of the graph
{0:[1], 1:[0,2], 2:[1,3], 3:[2]}	[1,2]	Removing nodes 1 or 2 disconnects the chain
{0:[1,2], 1:[0], 2:[0]}	[0]	Node 0 connects two leaf nodes
{0:[1], 1:[0]}	[]	Two nodes connected by a single edge, neither is an articulation point
{0:[1,2], 1:[0,2], 2:[0,1]}	[]	Triangle graph, fully connected — no articulation points

Explore Articulation Points

Load an example or enter your own input. Use the player controls to follow each change.

Understanding the Problem

We are given an undirected graph. Our goal is to find all the articulation points in this graph. An articulation point (or cut vertex) is a node that, if removed, increases the number of connected components in the graph.

In simple terms, these are the critical nodes that hold parts of the graph together. If any of them are removed, some nodes may no longer be reachable from others.

This is especially useful in network design and fault-tolerant systems where you want to identify single points of failure.

Step-by-Step Solution with Example

step 1: Represent the graph

We begin by representing the graph using an adjacency list. For example, let's take this graph:

{
  0: [1, 2],
  1: [0, 2],
  2: [0, 1, 3, 5],
  3: [2, 4],
  4: [3],
  5: [2, 6, 8],
  6: [5, 7],
  7: [6],
  8: [5]
}

This graph has 9 nodes (0 to 8), and is connected in such a way that removing some nodes would disconnect parts of it.

step 2: Perform DFS traversal and track timestamps

We use Depth-First Search (DFS) to explore the graph and keep track of:

tin[u]: The discovery time of node u
low[u]: The lowest discovery time reachable from u or any of its descendants

We initialize both of these arrays with -1 and use a global timer to assign timestamps as we go.

step 3: Apply articulation point conditions during DFS

While traversing each node u, we apply the following logic:

Case 1 (Root): If u is the root of DFS and has more than one child, then u is an articulation point.
Case 2 (Bridge): If u is not root and there exists a child v such that low[v] >= tin[u], then u is an articulation point.

step 4: Update low values properly

After visiting a neighbor v of u, we update low[u] based on:

If v is a child: low[u] = min(low[u], low[v])
If v is already visited and is not parent of u: low[u] = min(low[u], tin[v])

step 5: Collect all articulation points

We use a boolean array isArticulation[u] to mark nodes that satisfy the above conditions. After DFS is complete, we collect all nodes marked as articulation points.

Edge Cases

Single Node: A graph with only one node has no articulation points.
Disconnected Graph: Apply DFS from every unvisited node to ensure all components are covered.
Tree Graph: In a tree, all non-leaf nodes (except the root with one child) can be articulation points.
Cyclic Graph: Presence of back edges affects the low values and prevents over-marking articulation points.

Finally

The key to solving this problem is understanding how DFS works in combination with discovery and low times. By tracking when we visit a node and the lowest point reachable from it, we can detect where the graph would split if a node is removed.

This method is efficient (O(V + E)) and elegant, using classic DFS with a few smart checks to find critical points in any connected or disconnected undirected graph.

Initialize tin[], low[], visited[], and timer to track DFS discovery times.
Perform DFS traversal starting from any node.
For each unvisited child v of u:

Call DFS recursively on v.
Update low[u] = min(low[u], low[v]).
Check articulation conditions for u.

For visited child v (not parent), update low[u] = min(low[u], tin[v]).
Collect all articulation points from marked vertices.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100

int timer = 0;
int tin[MAX_VERTICES], low[MAX_VERTICES];
bool visited[MAX_VERTICES], isArticulation[MAX_VERTICES];

void dfs(int u, int parent, int V, int adj[][MAX_VERTICES]) {
    visited[u] = true;
    tin[u] = low[u] = timer++;
    int children = 0;

    for (int v = 0; v < V; v++) {
        if (adj[u][v]) { // edge exists
            if (v == parent) continue;
            if (visited[v]) {
                if (tin[v] < low[u]) low[u] = tin[v];
            } else {
                dfs(v, u, V, adj);
                if (low[v] < low[u]) low[u] = low[v];
                if (low[v] >= tin[u] && parent != -1) isArticulation[u] = true;
                children++;
            }
        }
    }

    if (parent == -1 && children > 1) isArticulation[u] = true;
}

int main() {
    int V = 6;
    int adj[MAX_VERTICES][MAX_VERTICES] = {0};

    // Graph edges
    adj[0][1] = 1; adj[1][0] = 1;
    adj[0][2] = 1; adj[2][0] = 1;
    adj[1][2] = 1; adj[2][1] = 1;
    adj[2][3] = 1; adj[3][2] = 1;
    adj[3][4] = 1; adj[4][3] = 1;
    adj[3][5] = 1; adj[5][3] = 1;

    for (int i = 0; i < V; i++) {
        visited[i] = false;
        isArticulation[i] = false;
        tin[i] = -1;
        low[i] = -1;
    }

    for (int i = 0; i < V; i++) {
        if (!visited[i]) dfs(i, -1, V, adj);
    }

    printf("Articulation Points: ");
    for (int i = 0; i < V; i++) {
        if (isArticulation[i]) printf("%d ", i);
    }
    printf("\n");

    return 0;
}

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

int timer = 0;
vector<int> tin, low;
vector<bool> visited, isArticulation;
vector<vector<int>> adj;

void dfs(int u, int parent) {
    visited[u] = true;
    tin[u] = low[u] = timer++;
    int children = 0;

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

    if (parent == -1 && children > 1) isArticulation[u] = true;
}

int main() {
    int V = 6;
    adj.resize(V);
    tin.resize(V, -1);
    low.resize(V, -1);
    visited.resize(V, false);
    isArticulation.resize(V, false);

    // Graph edges
    adj[0] = {1, 2};
    adj[1] = {0, 2};
    adj[2] = {0, 1, 3};
    adj[3] = {2, 4, 5};
    adj[4] = {3};
    adj[5] = {3};

    for (int i = 0; i < V; i++) {
        if (!visited[i]) dfs(i, -1);
    }

    cout << "Articulation Points: ";
    for (int i = 0; i < V; i++) {
        if (isArticulation[i]) cout << i << " ";
    }
    cout << endl;

    return 0;
}

Python implementation

def find_articulation_points(V, adj):
    timer = 0
    tin = [-1] * V
    low = [-1] * V
    visited = [False] * V
    is_articulation = [False] * V

    def dfs(u, parent):
        nonlocal timer
        visited[u] = True
        tin[u] = low[u] = timer
        timer += 1
        children = 0

        for v in adj[u]:
            if v == parent:
                continue
            if visited[v]:
                low[u] = min(low[u], tin[v])
            else:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] >= tin[u] and parent != -1:
                    is_articulation[u] = True
                children += 1

        if parent == -1 and children > 1:
            is_articulation[u] = True

    for i in range(V):
        if not visited[i]:
            dfs(i, -1)

    return [i for i, val in enumerate(is_articulation) if val]


graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3],
    3: [2, 4, 5],
    4: [3],
    5: [3]
}
V = len(graph)
articulation_points = find_articulation_points(V, graph)
print("Articulation Points:", articulation_points)

Java implementation

import java.util.*;

public class ArticulationPoints {
    private static int timer = 0;
    private static int[] tin, low;
    private static boolean[] visited, isArticulation;
    private static List<List<Integer>> adj;

    private static void dfs(int u, int parent) {
        visited[u] = true;
        tin[u] = low[u] = timer++;
        int children = 0;

        for (int v : adj.get(u)) {
            if (v == parent) continue;
            if (visited[v]) {
                low[u] = Math.min(low[u], tin[v]);
            } else {
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] >= tin[u] && parent != -1) isArticulation[u] = true;
                children++;
            }
        }

        if (parent == -1 && children > 1) isArticulation[u] = true;
    }

    public static void main(String[] args) {
        int V = 6;
        tin = new int[V];
        low = new int[V];
        visited = new boolean[V];
        isArticulation = new boolean[V];

        adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());

        // Graph edges
        adj.get(0).addAll(Arrays.asList(1, 2));
        adj.get(1).addAll(Arrays.asList(0, 2));
        adj.get(2).addAll(Arrays.asList(0, 1, 3));
        adj.get(3).addAll(Arrays.asList(2, 4, 5));
        adj.get(4).add(3);
        adj.get(5).add(3);

        for (int i = 0; i < V; i++) {
            if (!visited[i]) dfs(i, -1);
        }

        System.out.print("Articulation Points: ");
        for (int i = 0; i < V; i++) {
            if (isArticulation[i]) System.out.print(i + " ");
        }
        System.out.println();
    }
}

JavaScript implementation

function findArticulationPoints(V, adj) {
  let timer = 0;
  const tin = new Array(V).fill(-1);
  const low = new Array(V).fill(-1);
  const visited = new Array(V).fill(false);
  const isArticulation = new Array(V).fill(false);

  function dfs(u, parent) {
    visited[u] = true;
    tin[u] = low[u] = timer++;
    let children = 0;

    for (const v of adj[u]) {
      if (v === parent) continue;
      if (visited[v]) {
        low[u] = Math.min(low[u], tin[v]);
      } else {
        dfs(v, u);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] >= tin[u] && parent !== -1) {
          isArticulation[u] = true;
        }
        children++;
      }
    }

    if (parent === -1 && children > 1) {
      isArticulation[u] = true;
    }
  }

  for (let i = 0; i < V; i++) {
    if (!visited[i]) {
      dfs(i, -1);
    }
  }

  const result = [];
  for (let i = 0; i < V; i++) {
    if (isArticulation[i]) result.push(i);
  }
  return result;
}

const graph = {
  0: [1, 2],
  1: [0, 2],
  2: [0, 1, 3],
  3: [2, 4, 5],
  4: [3],
  5: [3]
};

const V = Object.keys(graph).length;
console.log("Articulation Points:", findArticulationPoints(V, graph));

Go implementation

package main

import (
	"fmt"
)

var timer int
var tin, low []int
var visited, isArticulation []bool
var adj [][]int

func dfs(u, parent int) {
	visited[u] = true
	tin[u], low[u] = timer, timer
	timer++
	children := 0

	for _, v := range adj[u] {
		if v == parent {
			continue
		}
		if visited[v] {
			if tin[v] < low[u] {
				low[u] = tin[v]
			}
		} else {
			dfs(v, u)
			if low[v] < low[u] {
				low[u] = low[v]
			}
			if low[v] >= tin[u] && parent != -1 {
				isArticulation[u] = true
			}
			children++
		}
	}

	if parent == -1 && children > 1 {
		isArticulation[u] = true
	}
}

func main() {
	V := 6
	tin = make([]int, V)
	low = make([]int, V)
	visited = make([]bool, V)
	isArticulation = make([]bool, V)
	adj = make([][]int, V)

	adj[0] = []int{1, 2}
	adj[1] = []int{0, 2}
	adj[2] = []int{0, 1, 3}
	adj[3] = []int{2, 4, 5}
	adj[4] = []int{3}
	adj[5] = []int{3}

	for i := 0; i < V; i++ {
		if !visited[i] {
			dfs(i, -1)
		}
	}

	fmt.Print("Articulation Points: ")
	for i := 0; i < V; i++ {
		if isArticulation[i] {
			fmt.Printf("%d ", i)
		}
	}
	fmt.Println()
}

Rust implementation

use std::cmp;

fn dfs(
    u: usize,
    parent: Option<usize>,
    timer: &mut i32,
    tin: &mut Vec<i32>,
    low: &mut Vec<i32>,
    visited: &mut Vec<bool>,
    is_articulation: &mut Vec<bool>,
    adj: &Vec<Vec<usize>>
) {
    visited[u] = true;
    tin[u] = *timer;
    low[u] = *timer;
    *timer += 1;
    let mut children = 0;

    for &v in &adj[u] {
        if Some(v) == parent {
            continue;
        }
        if visited[v] {
            low[u] = cmp::min(low[u], tin[v]);
        } else {
            dfs(v, Some(u), timer, tin, low, visited, is_articulation, adj);
            low[u] = cmp::min(low[u], low[v]);
            if low[v] >= tin[u] && parent.is_some() {
                is_articulation[u] = true;
            }
            children += 1;
        }
    }

    if parent.is_none() && children > 1 {
        is_articulation[u] = true;
    }
}

fn main() {
    let V = 6;
    let mut timer = 0;
    let mut tin = vec![-1; V];
    let mut low = vec![-1; V];
    let mut visited = vec![false; V];
    let mut is_articulation = vec![false; V];

    let adj = vec![
        vec![1, 2],
        vec![0, 2],
        vec![0, 1, 3],
        vec![2, 4, 5],
        vec![3],
        vec![3],
    ];

    for i in 0..V {
        if !visited[i] {
            dfs(i, None, &mut timer, &mut tin, &mut low, &mut visited, &mut is_articulation, &adj);
        }
    }

    print!("Articulation Points: ");
    for i in 0..V {
        if is_articulation[i] {
            print!("{} ", i);
        }
    }
    println!();
}

Kotlin implementation

fun main() {
    val V = 6
    val adj = Array(V) { mutableListOf<Int>() }

    adj[0].addAll(listOf(1, 2))
    adj[1].addAll(listOf(0, 2))
    adj[2].addAll(listOf(0, 1, 3))
    adj[3].addAll(listOf(2, 4, 5))
    adj[4].add(3)
    adj[5].add(3)

    val tin = IntArray(V) { -1 }
    val low = IntArray(V) { -1 }
    val visited = BooleanArray(V) { false }
    val isArticulation = BooleanArray(V) { false }
    var timer = 0

    fun dfs(u: Int, parent: Int) {
        visited[u] = true
        tin[u] = timer
        low[u] = timer
        timer++
        var children = 0

        for (v in adj[u]) {
            if (v == parent) continue
            if (visited[v]) {
                low[u] = minOf(low[u], tin[v])
            } else {
                dfs(v, u)
                low[u] = minOf(low[u], low[v])
                if (low[v] >= tin[u] && parent != -1) {
                    isArticulation[u] = true
                }
                children++
            }
        }

        if (parent == -1 && children > 1) {
            isArticulation[u] = true
        }
    }

    for (i in 0 until V) {
        if (!visited[i]) dfs(i, -1)
    }

    print("Articulation Points: ")
    for (i in 0 until V) {
        if (isArticulation[i]) print("$i ")
    }
    println()
}

Swift implementation

import Foundation

var timer = 0
var tin = [Int]()
var low = [Int]()
var visited = [Bool]()
var isArticulation = [Bool]()
var adj = [[Int]]()

func dfs(_ u: Int, _ parent: Int) {
    visited[u] = true
    tin[u] = timer
    low[u] = timer
    timer += 1
    var children = 0

    for v in adj[u] {
        if v == parent { continue }
        if visited[v] {
            low[u] = min(low[u], tin[v])
        } else {
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if low[v] >= tin[u] && parent != -1 {
                isArticulation[u] = true
            }
            children += 1
        }
    }

    if parent == -1 && children > 1 {
        isArticulation[u] = true
    }
}

let V = 6

// Initialize arrays
tin = Array(repeating: -1, count: V)
low = Array(repeating: -1, count: V)
visited = Array(repeating: false, count: V)
isArticulation = Array(repeating: false, count: V)
adj = Array(repeating: [Int](), count: V)

// Define graph
adj[0] = [1, 2]
adj[1] = [0, 2]
adj[2] = [0, 1, 3]
adj[3] = [2, 4, 5]
adj[4] = [3]
adj[5] = [3]

for i in 0..<V {
    if !visited[i] {
        dfs(i, -1)
    }
}

print("Articulation Points: ", terminator: "")
for i in 0..<V {
    if isArticulation[i] {
        print(i, terminator: " ")
    }
}
print()

TypeScript implementation

function findArticulationPoints(V: number, adj: Record<number, number[]>): number[] {
  let timer = 0;
  const tin: number[] = Array(V).fill(-1);
  const low: number[] = Array(V).fill(-1);
  const visited: boolean[] = Array(V).fill(false);
  const isArticulation: boolean[] = Array(V).fill(false);

  function dfs(u: number, parent: number) {
    visited[u] = true;
    tin[u] = low[u] = timer++;
    let children = 0;

    for (const v of adj[u]) {
      if (v === parent) continue;
      if (visited[v]) {
        low[u] = Math.min(low[u], tin[v]);
      } else {
        dfs(v, u);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] >= tin[u] && parent !== -1) {
          isArticulation[u] = true;
        }
        children++;
      }
    }

    if (parent === -1 && children > 1) {
      isArticulation[u] = true;
    }
  }

  for (let i = 0; i < V; i++) {
    if (!visited[i]) dfs(i, -1);
  }

  const result: number[] = [];
  for (let i = 0; i < V; i++) {
    if (isArticulation[i]) result.push(i);
  }
  return result;
}

const graph: Record<number, number[]> = {
  0: [1, 2],
  1: [0, 2],
  2: [0, 1, 3],
  3: [2, 4, 5],
  4: [3],
  5: [3]
};

const V = Object.keys(graph).length;
console.log("Articulation Points:", findArticulationPoints(V, graph));