What Is an Articulation Point? The Graph Concept Behind Critical Connections

Your network has 500 nodes and thousands of connections. One node fails. The whole thing splits in two. Not because of a bug. Not because of a deploy. Just because that one node happened to be the thing holding everything together, and now it's gone, and you are having a very bad morning.

That node is an articulation point. Every interview question about "critical nodes" and every system design question about "single points of failure" is really asking you to find it.

An articulation point (also called a cut vertex) is a vertex in an undirected graph whose removal increases the number of connected components. Remove any other vertex and the graph stays in one piece. Remove this one and it fractures.

This concept shows up directly in LeetCode 1192 (Critical Connections in a Network), in network reliability problems, and anywhere a system design interviewer asks you to identify structural weak spots.

A Concrete Example First

Here is a small graph:

0 --- 1 --- 3 --- 4
      |
      2

Which nodes, if removed, disconnect this graph?

Remove node 0: nodes {1, 2, 3, 4} stay connected. Not an articulation point. Node 0 is fine, just vibing.

Remove node 1: the graph splits into {0} on one side and {2, 3, 4} on the other. No path connects them without going through 1. Articulation point.

Remove node 3: the graph splits into {0, 1, 2} and {4}. Articulation point.

Nodes 1 and 3 are the structural bottlenecks. The places where connectivity hangs by a thread. The nodes whose oncall rotation should probably pay more.

Why the Naive Approach Fails

The obvious algorithm: for each vertex, remove it, then run BFS or DFS to check if the rest of the graph stays connected.

That is O(V · (V + E)). For a network with 10,000 nodes and 50,000 edges, you are looking at 500 million operations. Your interviewer will be very politely nodding while internally marking the "time management" box as a concern.

You need to find all articulation points in a single DFS pass.

The Discovery Time Insight

The efficient algorithm comes from Robert Tarjan's 1972 work on DFS tree properties. It runs in O(V + E) by tracking two values for every node as DFS progresses.

disc[u] is the discovery time when DFS first visits node u. Nodes get numbered in the order DFS reaches them.

low[u] is the lowest discovery time reachable from the subtree rooted at u, using both DFS tree edges and back edges. A back edge connects a node to one of its ancestors in the DFS tree, bypassing the tree path.

Think of low[u] as asking: "from this node and everything below it, how far back up can we reach?" If the answer is far up, there are escape routes. If the answer is only as far as the current node, there is no escape. The current node is a bottleneck. It is load-bearing. It is the one engineer who knows how the payment system works.

How low[u] Gets Computed

When DFS visits node u with parent p:

low[u] = disc[u]   # start with own discovery time

for each neighbor v of u:
    if v is unvisited:
        run dfs(v)
        low[u] = min(low[u], low[v])   # child's reach becomes your reach
    elif v != p:
        low[u] = min(low[u], disc[v])  # back edge: reach v's discovery time

The v != p check is not optional. In an undirected graph, every edge appears in both directions. When you see your parent p as a neighbor, that is just the edge you came from, not a back edge. Skip it. Treat it as a real back edge and every node looks like it can escape when it cannot. You will find zero articulation points. Your graph will look suspiciously healthy. It is not.

The Two Conditions for an Articulation Point

Case 1: u is the DFS root and has two or more DFS tree children.

If the root has only one child, the whole subtree stays connected after removing the root. Two or more children means two separate subtrees with no direct edge between them (if there were one, DFS would have discovered both children from the same side). Remove the root and they disconnect. The root case is its own special rule, and it is the one candidates forget most reliably.

Case 2: u is not the DFS root, and it has a child v where low[v] >= disc[u].

This says: from v and everything below it, there is no back edge reaching above u. The only path from v's subtree to the rest of the graph goes through u. Remove u and that subtree is stranded.

If low[v] < disc[u], a back edge somewhere in v's subtree reaches above u. That back edge keeps the subtree connected even without u. The subtree has a fire escape.

Implementation

def find_articulation_points(graph: dict[int, list[int]], n: int) -> list[int]:
    disc = [-1] * n
    low = [-1] * n
    parent = [-1] * n
    is_ap = [False] * n
    timer = [0]

    def dfs(u: int) -> None:
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        children = 0

        for v in graph[u]:
            if disc[v] == -1:
                children += 1
                parent[v] = u
                dfs(v)
                low[u] = min(low[u], low[v])

                if parent[u] == -1 and children > 1:
                    is_ap[u] = True
                if parent[u] != -1 and low[v] >= disc[u]:
                    is_ap[u] = True
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    for i in range(n):
        if disc[i] == -1:
            dfs(i)

    return [i for i in range(n) if is_ap[i]]

The outer loop handles disconnected graphs. If your input is already in pieces before you start, you still want articulation points in each component.

Using disc[i] == -1 to identify unvisited nodes eliminates the need for a separate visited array since unvisited nodes always have disc == -1. One less array. Treat yourself.

One practical note: Python's default recursion limit is 1,000 frames. A path graph with 1,001 nodes will hit it. You will get a RecursionError mid-DFS and a fun debugging session. For interview problems with tight constraints, convert to an explicit iterative DFS using a stack on the heap.

Tracing Through the Example

Return to the original graph and watch the algorithm run.

0 --- 1 --- 3 --- 4
      |
      2

DFS starts at 0. Discovery order: 0 → 1 → 3 → 4, then backtrack to 3, backtrack to 1, visit 2.

Node	disc	low (final)
0	0	0
1	1	0
3	2	2
4	3	3
2	4	1

Node 0 is the DFS root with one child. The root case requires two or more children. Not an articulation point. Node 0 is not load-bearing. It can take the day off.

Node 1 is not the root. Check child 3: low[3] = 2 >= disc[1] = 1. True. Articulation point. (Child 2 also triggers it: low[2] = 1 >= disc[1] = 1.)

Node 3 is not the root. Check child 4: low[4] = 3 >= disc[3] = 2. True. Articulation point.

Result: {1, 3}. Correct.

Articulation Points vs Bridges

A bridge is an edge (u, v) whose removal disconnects the graph. The condition: low[v] > disc[u] (strict greater than).

An articulation point uses: low[v] >= disc[u] (greater than or equal).

The difference in symbol corresponds to a real difference in structure. When low[v] == disc[u], a back edge from v's subtree reaches exactly u, creating a cycle. That cycle means the edge (u, v) is not a bridge since there is an alternate path. But u is still an articulation point because removing the vertex strands the subtree.

Bridges use strict >. Articulation points use >=. One character. Two completely different answers. Do not mix them up in an interview. It will not go the way you hope.

The post Bridges and Articulation Points walks through both with full implementations side by side.

Time and Space Complexity

Dimension	Complexity
Time	O(V + E)
Space	O(V)

Every node is visited exactly once. Every edge is examined at most twice, once from each endpoint. The low update adds constant work per edge. The DFS call stack reaches O(V) in the worst case on a path graph.

Interview Applications

Pattern recognition. The signal for articulation points is any question asking which vertices are "critical," "essential," or "bottlenecks" for graph connectivity. The phrasing changes. The algorithm does not. See Depth-First Search Algorithm for the DFS mechanics underlying this.

LeetCode 1192. The problem is framed around edges (critical connections = bridges), not vertices. But candidates who understand articulation points handle the bridge variant easily because the disc/low framework is identical. The implementation differs by one character. That character you now know.

Network design questions. "Which nodes in this dependency graph are single points of failure?" is an articulation point question. The graph is your service dependency map. The articulation points are the services you need to make redundant before your on-call rotation becomes a recurring nightmare. Connected Components covers the underlying connectivity model.

Common mistakes under pressure:

The root exception trips people up most often. Candidates apply the low[v] >= disc[u] check to the root and wonder why nodes are being flagged that should not be. The root needs its own child-count logic because it has no parent to anchor the back-edge comparison. It is a special snowflake. Treat it like one.

Using > instead of >= gives you bridges when you want articulation points. Forgetting v != parent makes every non-leaf look like an articulation point because the parent edge gives an artificially low low value. Both bugs produce code that runs confidently and completely wrong.

If you want to catch these gaps before your actual interview, SpaceComplexity offers voice-based mock sessions where an AI interviewer asks you to explain the algorithm out loud. That is exactly where the root-exception blind spot tends to surface: when you have to say the condition out loud instead of just typing it.