Finding Articulation Points

March 2026 · 22 min read

What is an Articulation Point

An articulation point (also called a cut vertex) is a vertex in an undirected graph whose removal, along with all its incident edges, increases the number of connected components.

In practical terms: if you remove an articulation point from a connected graph, the graph splits into two or more disconnected pieces. These are the critical nodes in a network. If a router is an articulation point, losing it partitions the network.

Vertex 2 is an articulation point. Remove it and the graph splits into two components: {0, 1, 5} and {3, 4, 6}. No other single vertex removal disconnects this graph.

Difference from Bridges

Bridges and articulation points are closely related, but they are fundamentally different objects:

Relationship: If edge (u, v) is a bridge where v is not a leaf, then both u and v are articulation points. If v is a leaf (degree 1), only u is an articulation point. However, an articulation point does not necessarily lie on a bridge. Consider a node connecting two cycles: removing that node splits the graph, but no single edge is a bridge.

Vertex D is an articulation point (removing it separates {A, B, C} from {E, F}), but the graph has no bridges because every edge belongs to a cycle (through B-D) or the 3-cycle structures. The edge B-D is a bridge, and both B and D are APs. This shows the concepts are related but distinct.

The Two Conditions for Articulation Points

Like bridges, we use DFS discovery times (disc[]) and low-link values (low[]). But the detection conditions differ.

A vertex u is an articulation point if either of these conditions holds:

Condition 1: Root of the DFS tree

If u is the root of the DFS tree (meaning parent == -1) and u has two or more children in the DFS tree, then u is an articulation point.

Why? The root has no ancestor. If it has two children, those children are in separate subtrees. The only path between them goes through the root. Remove the root, and those subtrees become disconnected.

Condition 2: Non-root vertex

If u is not the root and has a child v in the DFS tree such that:

low[v] >= disc[u]

then u is an articulation point.

This means: no vertex in v's subtree can reach any ancestor of u (or even u itself) through a back edge without going through u. So removing u disconnects v's entire subtree from the rest of the graph.

Why >= Instead of >

This is the most common source of confusion. For bridges, the condition is low[v] > disc[u] (strict inequality). For articulation points, the condition is low[v] >= disc[u] (non-strict). Why the difference?

Consider a non-root vertex u with child v. Suppose v has a back edge reaching exactly u itself, so low[v] == disc[u].

For bridges: Edge (u, v) is not a bridge because low[v] == 1 == disc[u], which is not strictly greater. Correct: removing the edge u-v does not disconnect the graph since w can still reach u through the back edge.

For articulation points: Vertex u is an AP because low[v] == 1 >= disc[u] == 1. Correct: removing vertex u (and all its edges, including the back edge w to u) disconnects v and w from a. The back edge from w went to u itself, not past u to a. So v's subtree has no way to reach a.

The Two Updates of low[] — In Detail

In both bridge and articulation point detection, the DFS updates low[u] in exactly two places. Understanding both deeply is essential for getting the algorithm right — and for explaining it in interviews. The two updates are identical for bridges and APs; only the detection condition differs (> vs >=).

if (disc[v] == -1) {           // v is unvisited — tree edge
    dfs(v, u);
    low[u] = min(low[u], low[v]);   // ← UPDATE 2: child return
} else if (v != parent) {       // v already visited — back edge
    low[u] = min(low[u], disc[v]);  // ← UPDATE 1: back edge
}

Update 1: Back Edge → low[u] = min(low[u], disc[v])

When it fires: Node u encounters an already-visited, non-parent neighbor v. This is a back edge — a shortcut from u to an ancestor v in the DFS tree.

What it means: “I, node u, have a direct shortcut to ancestor v.”

Why disc[v] and not low[v]? The back edge goes to v, not through v’s subtree. Writing disc[v] says: “I can reach the node discovered at time disc[v].” Using low[v] would be wrong because low[v] encodes reachability through v’s subtree — but the back edge does not traverse v’s subtree at all.

Update 2: Child Return → low[u] = min(low[u], low[v])

When it fires: The DFS finishes exploring child v and returns to parent u.

What it means: “Everything v’s subtree can reach, I can reach too — via the tree edge u → v.”

Why low[v] here? low[v] is the complete summary of the earliest ancestor reachable from v’s entire subtree. This propagation is how back-edge information flows upward through the DFS tree. Using disc[v] here would throw away all of v’s subtree’s reachability information — every back edge discovered deeper in the tree would be lost.

Why Using low[v] for Back Edges Breaks AP Detection

This is the subtlety that trips people up. Let’s see exactly how using low[v] instead of disc[v] for back edges produces a wrong answer.

Consider this graph with 6 nodes. The DFS tree edges are solid green; back edges are dashed purple. Node B is an articulation point — removing it disconnects {A} from {C,D} and {E,F}.

The critical moment is when F processes its back edge to B. By the time DFS reaches F, the first subtree (C → D) has already been explored, and B’s low value has been updated to 0 (propagated from D’s back edge to A).

The bug: low[B] is 0 because B’s other child (C’s subtree) propagated D’s back edge to A. When F uses low[B], it inherits reachability that flows through B and through a completely different subtree. But if B is removed, that entire path vanishes — the back edge D → A goes through B’s subtree, and node F has no connection to it.

Interactive Animation: Both Updates in Action

This animation traces the DFS on a 7-node graph, labelling every low[] update as either Update 1 (back edge) or Update 2 (child propagation). Watch how the back edge at node 5 is discovered once, then propagated upward through four successive child returns.

The Algorithm

The algorithm is a modification of the bridge-finding DFS. We track disc[] and low[] as before, plus a boolean array isAP[] marking articulation points, and a child count for the root check.

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

void apDFS(int u, int parent, vector<vector<int>>& adj,
           vector<int>& disc, vector<int>& low, int& timer,
           vector<bool>& isAP) {
    disc[u] = low[u] = timer++;
    int children = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        if (disc[v] == -1) {
            children++;
            apDFS(v, u, adj, disc, low, timer, isAP);
            low[u] = min(low[u], low[v]);
            if (parent == -1 && children > 1) isAP[u] = true;
            if (parent != -1 && low[v] >= disc[u]) isAP[u] = true;
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
}

vector<int> findArticulationPoints(int n, vector<vector<int>>& adj) {
    vector<int> disc(n, -1), low(n, -1);
    vector<bool> isAP(n, false);
    int timer = 0;
    for (int i = 0; i < n; i++) {
        if (disc[i] == -1) {
            apDFS(i, -1, adj, disc, low, timer, isAP);
        }
    }
    vector<int> result;
    for (int i = 0; i < n; i++) {
        if (isAP[i]) result.push_back(i);
    }
    return result;
}

Key differences from bridge detection:

• We track children count for each vertex during DFS
• Root check: parent == -1 && children > 1
• Non-root check: low[v] >= disc[u] (not strictly >)
• We mark the vertex as AP rather than an edge as a bridge

Step-by-Step Walkthrough

We trace the algorithm on a graph with 8 vertices (0 through 7) and 10 edges. The graph has two articulation points: vertex 1 and vertex 3. Use the step buttons to advance through each DFS action.

Common Mistakes & Conceptual Pitfalls

Below are the eight most common mistakes when implementing Tarjan's articulation point algorithm. Each one maps to a real conceptual gap — not just a typo. Understanding why each mistake is wrong will cement the algorithm in your head so you never make them again.

Mistake 1: Treating low[u] as Local to Node u

This is the root of several downstream confusions. When you write:

low[source] = min(low[source], low[child]);

it feels strange — "why am I updating my low with my child's low?" The answer: low[source] is not "source's personal reachability." It is the minimum discovery time reachable from the entire subtree rooted at source, including all descendants.

• low[source] starts as disc[source] — worst case: source can only "reach" itself
• It improves if source finds a direct back edge to an ancestor: min(low[source], disc[ancestor])
• It improves if any child's subtree can reach something earlier: min(low[source], low[child])

The child propagation is what makes low[] a subtree-level summary, not a node-level one. Once you internalize this, the child return update becomes completely intuitive: "my child explored a subtree and the best it found was low[child]; since I own that subtree, I inherit that result."

Mistake 2: Using low[v] Instead of disc[v] for Back Edges

This is the most dangerous mistake because it sometimes gives correct results (for bridges) but silently fails for articulation points. The back edge from source to adj_node proves that source can reach adj_node directly — nothing more. Using low[adj_node] would "borrow" reachability from adj_node's subtree, which goes through adj_node. But if we later check whether adj_node is an AP (by removing it and all its edges), that borrowed path is destroyed.

// Back edge: visited non-parent
low[source] = min(low[source],
                  low[adj_node]); // ✗

// Back edge: visited non-parent
low[source] = min(low[source],
                  disc[adj_node]); // ✓

See the Two Updates of low[] section above for a detailed counterexample showing exactly how this bug causes a missed articulation point.

Mistake 3: Getting the Articulation Condition Wrong

The correct non-root AP condition is:

low[child] >= disc[source]

Here is what each side means and why the comparison is >=:

• Left: low[child] — "The earliest ancestor reachable from child's entire subtree." This is the scout report from below.
• Right: disc[source] — "When was source discovered?" This is the escape threshold. If the child's subtree can reach something discovered before source (an ancestor of source), the subtree has an escape route that bypasses source.
• >= — If low[child] equals disc[source], the subtree can reach source itself but not past it. Removing source removes all edges to source, so the subtree is stranded. If low[child] is strictly greater, the subtree can't even reach source. Either way: source is an AP.

Common wrong versions and why they fail:

Mistake 4: Applying Non-Root Logic to the Root

The root node has completely different AP logic. The two cases are entirely separate:

if (parent != -1
    && low[child] >= disc[source])
    isAP[source] = true;

if (parent == -1 && children > 1)
    isAP[source] = true;

Why non-root check fails for root: For the root (disc[root] = 0 typically), low[child] >= 0 is always true since low values are non-negative. The non-root condition would flag every root with at least one child as an AP — which is wrong. A root with one DFS-tree child is never an AP.

Mistake 5: Counting All Non-Parent Neighbors as DFS Children

In the DFS tree, a child of u is a neighbor v that was unvisited when we explored edge u→v, causing us to recurse into v. Already-visited non-parent neighbors are connected by back edges — they are ancestors, not children.

for (int v : adj[u]) {
  if (v == parent) continue;
  children++; // ✗ counts back edges
  if (disc[v] == -1) {
    dfs(v, u);
    // ...
  } else {
    low[u] = min(low[u], disc[v]);
  }
}

for (int v : adj[u]) {
  if (v == parent) continue;
  if (disc[v] == -1) {
    children++; // ✓ only tree children
    dfs(v, u);
    // ...
  } else {
    low[u] = min(low[u], disc[v]);
  }
}

This matters for the root check: children > 1 must count only DFS tree children. If you count back-edge neighbors, a root with one tree child and one back-edge neighbor would be falsely flagged as an AP.

Mistake 6: Checking the AP Condition Before Absorbing the Child's Low

This mistake does not affect correctness of the AP check itself — because the AP condition uses low[child], not low[source]. However, it reveals a flawed mental model and can corrupt low[source] if you later rely on it. The correct conceptual flow is:

1. DFS(child) returns — child's low value is now fully computed
2. Absorb child's reachability: low[source] = min(low[source], low[child])
3. Check the AP condition: if (low[child] >= disc[source]) → AP

dfs(child, source);                             // 1. explore
low[source] = min(low[source], low[child]);     // 2. absorb
if (parent != -1 && low[child] >= disc[source]) // 3. check
    isAP[source] = true;

If you understand the algorithm as "first absorb, then check," you naturally see the check asks: "now that I know what child's subtree can reach, does it reach above me?" Placing the check first suggests mechanical formula application without understanding the tree/back-edge story.

Mistake 7: Pushing Instead of Marking (Duplicate APs)

A single vertex can trigger the AP condition multiple times — once for each child whose subtree can't escape past it. If node u has three such children, the push approach adds u three times.

if (low[v] >= disc[u])
  result.push_back(u); // ✗

if (low[v] >= disc[u])
  isAP[u] = true; // ✓ idempotent
// After all DFS calls:
for (int i = 0; i < n; i++)
  if (isAP[i]) result.push_back(i);

Use vector<bool> isAP(n, false) and set isAP[u] = true. Collect results at the end. Setting true again does nothing — it's idempotent.

Mistake 8: Forgetting Disconnected Graphs

If the graph has multiple connected components, a single DFS from node 0 only explores node 0's component. Articulation points in other components are missed entirely.

// Always wrap DFS in a loop over all nodes:
for (int i = 0; i < n; i++) {
    if (disc[i] == -1) {             // unvisited = new component
        dfs(i, -1, adj, disc, low, timer, isAP);
    }
}

Each call to dfs(i, -1, ...) starts a new DFS tree for a new connected component. Node i becomes the root of that tree, so the root AP check (children > 1) applies to it. The timer is not reset between components — it continues incrementing globally, which is fine since disc values just need to be unique and monotonically increasing.

Combined Bridge and AP Detection

Bridges and articulation points can be found in the same DFS pass. The only difference is the comparison operator and what we record.

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

void findBridgesAndAPs(int u, int parent,
                       vector<vector<int>>& adj,
                       vector<int>& disc, vector<int>& low,
                       int& timer, vector<bool>& isAP,
                       vector<pair<int,int>>& bridges) {
    disc[u] = low[u] = timer++;
    int children = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        if (disc[v] == -1) {
            children++;
            findBridgesAndAPs(v, u, adj, disc, low,
                              timer, isAP, bridges);
            low[u] = min(low[u], low[v]);

            // Bridge check: strict inequality
            if (low[v] > disc[u]) {
                bridges.push_back({u, v});
            }

            // AP check: root case
            if (parent == -1 && children > 1) {
                isAP[u] = true;
            }
            // AP check: non-root case (non-strict)
            if (parent != -1 && low[v] >= disc[u]) {
                isAP[u] = true;
            }
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
}

void solve(int n, vector<vector<int>>& adj) {
    vector<int> disc(n, -1), low(n, -1);
    vector<bool> isAP(n, false);
    vector<pair<int,int>> bridges;
    int timer = 0;

    for (int i = 0; i < n; i++) {
        if (disc[i] == -1) {
            findBridgesAndAPs(i, -1, adj, disc, low,
                              timer, isAP, bridges);
        }
    }

    // bridges contains all bridge edges
    // isAP[v] is true for all articulation points
}

Both checks happen inside the same if (disc[v] == -1) block. The bridge check uses >, the AP check uses >=. The overhead of combining them is negligible: one extra comparison per tree edge.

Time and Space Complexity

The algorithm visits each vertex exactly once and examines each edge exactly twice (once from each endpoint). The total work is linear in the size of the graph, identical to standard DFS.

For very large graphs where the recursion depth might exceed the stack limit (path graphs with 10⁵+ vertices), convert to an iterative implementation using an explicit stack.