Articulation Points Finder

Pseudocode

One DFS, two numbers per vertex. The discovery time says when a vertex was first seen; the low-link says the earliest vertex its subtree can reach through a back edge.

dfs(u, parent):
    disc[u] = low[u] = ++time
    children = 0

    for each neighbor v of u:
        if v == parent: continue
        if v is visited:
            low[u] = min(low[u], disc[v])   // back edge
        else:
            children++
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if parent != NONE and low[v] >= disc[u]:
                mark u as an articulation point

    if parent == NONE and children > 1:
        mark u as an articulation point   // root rule

The condition low[v] >= disc[u] says the subtree rooted at the child v has no back edge climbing above u. So every route out of that subtree passes through u, and deleting u strands it. The root is a special case because it has no parent to be cut off from: the root is an articulation point exactly when it has two or more DFS children, since those subtrees can only reach each other through the root.

Worked example, step by step

Run the DFS from A on a graph made of a triangle with a two-node tail, taking neighbors alphabetically.

Example graph: Undirected edges A-B, B-C, C-A forming a triangle, plus C-D and D-E hanging off it.

1. Descend to E. disc and low are assigned on the way down: A gets 1, B gets 2, C gets 3, D gets 4, E gets 5. E is a leaf with only its parent D as a neighbor, so low[E] stays 5.
2. Return to D. low[D] = min(4, low[E] = 5) = 4. Test the child: low[E] = 5 >= disc[D] = 4, so nothing below E climbs above D. D is an articulation point, and indeed removing D isolates E.
3. Return to C. C also has the back edge C-A, which sets low[C] = min(3, disc[A] = 1) = 1. Folding in the child gives low[C] = min(1, low[D] = 4) = 1. Test the child D: low[D] = 4 >= disc[C] = 3, so C is an articulation point. Removing C severs the D-E tail from the triangle.
4. Return to B. low[B] = min(2, low[C] = 1) = 1. Test the child C: low[C] = 1 >= disc[B] = 2 is false, because C can reach all the way back to A without going through B. So B is not an articulation point, which is right: the triangle keeps A and C connected without it.
5. Finish at the root. A is the DFS root. It has exactly one DFS child, B, since C was reached through B rather than directly. One child means the root rule does not fire, so A is not an articulation point.

The articulation points are C and D. The triangle A-B-C has no articulation point among A and B because every vertex in a cycle has an alternative route, while the tail C-D-E is a chain in which every internal vertex is critical. That contrast is the intuition: articulation points live on chains, not inside cycles.

Complexity, and where it comes from

Time: O(V + E) · Space: O(V)

This is a single depth-first search with constant extra work per edge, so it costs the same as the traversal itself. Every vertex is visited once and every edge is examined twice, once from each endpoint. The extra state is two integers per vertex, the discovery time and the low-link, plus the recursion stack, all O(V). The naive alternative, removing each vertex in turn and testing connectivity, costs O(V times (V + E)), so the low-link method turns a quadratic check into a linear one in a single pass.

When to use Articulation Points, and when not to

Articulation points, bridges and biconnected components all come out of the same DFS. Which you want depends on whether the fragile thing is a vertex or an edge.

Common pitfalls

• Applying the non-root rule to the root. The root has no parent, so the low[v] >= disc[u] test is meaningless there and will usually mark it wrongly. The root needs its own rule: it is an articulation point exactly when it has two or more DFS children.
• Using low[v] instead of disc[v] on a back edge. When you meet an already visited vertex v, update with disc[v], not low[v]. Using low[v] can propagate a value from a different subtree and produce low-links that are too small, hiding genuine articulation points.
• Confusing the child test with the bridge test. Articulation points use low[v] >= disc[u]; bridges use low[v] > disc[u], strictly greater. The single character difference is the difference between "everything must pass through this vertex" and "everything must pass through this edge".
• Skipping the parent by identity rather than by edge. Comparing only the parent vertex id breaks on multigraphs. If two parallel edges join u and v, the second one is a genuine alternative route and must not be skipped. Track the edge you arrived on, not just the vertex.
• Forgetting disconnected components. A single DFS only covers one component. Loop over all vertices and start a new DFS from each unvisited one, resetting the root rule for each new root.

Frequently asked questions

What is an articulation point in a graph?

An articulation point, also called a cut vertex, is a vertex whose removal increases the number of connected components. In practical terms it is a single point of failure: every route between some pair of vertices passes through it, so deleting it splits the graph.

How do you find articulation points?

Run a single DFS recording for each vertex its discovery time and its low-link, the earliest discovery time reachable from its subtree via at most one back edge. A non-root vertex u is an articulation point if some DFS child v satisfies low[v] >= disc[u]. The root is one if it has two or more DFS children. The whole thing is O(V + E).

What is the difference between an articulation point and a bridge?

An articulation point is a vertex whose removal disconnects the graph; a bridge is an edge whose removal does. They come from the same DFS and differ by one comparison: low[v] >= disc[u] for articulation points, and the strict low[v] > disc[u] for bridges. A graph can have bridges but no articulation points, and vice versa.

Why is the root of the DFS a special case?

Because the general test asks whether a child subtree can reach above the current vertex, and there is nothing above the root. The root is only critical when it joins two or more otherwise separate subtrees, which is exactly the condition of having two or more DFS children.

What are articulation points used for?

They identify critical routers in communication networks, key junctions in road systems, servers whose failure would partition distributed infrastructure, and influential brokers in social networks. Reliability engineering uses them to decide where redundancy is worth the cost.