Articulation Points (Cut Vertices)

Articulation Points (also called cut vertices) are the single points of failure in a graph. Removing one of them splits the graph into disconnected pieces. Finding them in a single DFS is a classic graph interview question, and it teaches the disc/low technique that also powers bridges and strongly connected components.

The slow way first

The brute-force definition is literal: for each vertex, delete it, run a BFS/DFS over what remains, and check whether the graph is still connected. That is one full traversal per vertex, so O(V · (V + E)). Correct, but wasteful — we re-walk almost the whole graph V times.

The question to ask: can one DFS tell me, for each vertex, whether any of its descendants can escape past it without going through it? If a subtree has no such escape route, the vertex above it is a cut vertex.

The idea: disc and low in one DFS

Run a single DFS and stamp two numbers on every vertex:

• disc[u] — the time we first discovered u.
• low[u] — the smallest discovery time reachable from u using u subtree tree-edges plus at most one back edge.

For a non-root vertex u with a DFS child v: if low[v] >= disc[u], then v subtree has no back edge climbing above u, so u is the only way out — u is an articulation point. The root is special: it is a cut vertex exactly when it has two or more DFS children.

The key insight: low[v] >= disc[u] means the deepest the subtree can reach is u itself or lower in the tree — it cannot jump above u, so cutting u strands it.

Walk through it

Step through the animation. The DFS dives A → B → C → D → E, stamping disc = low as it goes. At E we find the back edge E — C, which pulls low[E] down to 2. Unwinding: D keeps a child with low < disc[D], so D is safe. But at C the child D has low = 2 >= disc[C] = 2, and at B the child C has low = 2 >= disc[B] = 1 — both fire the rule, so B and C light up red. The root A has only one child, so it is not a cut vertex.

Pseudocode

disc[*] = low[*] = -1; timer = 0; cuts = empty set
dfs(u, parent):
    disc[u] = low[u] = timer; timer += 1
    children = 0
    for v in neighbors(u):
        if disc[v] == -1:              # tree edge
            children += 1
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if parent != -1 and low[v] >= disc[u]:
                add u to cuts
        else if v != parent:           # back edge
            low[u] = min(low[u], disc[v])
    if parent == -1 and children > 1:  # root rule
        add u to cuts

The Python solution

def articulation_points(graph, n):
    disc = [-1] * n
    low = [-1] * n
    timer = [0]
    cuts = set()
 
    def dfs(u, parent):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        children = 0
        for v in graph[u]:
            if disc[v] == -1:
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if parent != -1 and low[v] >= disc[u]:
                    cuts.add(u)
            elif v != parent:
                low[u] = min(low[u], disc[v])
        if parent == -1 and children > 1:
            cuts.add(u)
    return cuts

• disc and low start at -1, which doubles as the unvisited marker.
• timer is a one-element list so the nested dfs can mutate it (a shared counter).
• On a tree edge (disc[v] == -1) we recurse, then relax low[u] with the child low[v].
• Line 15 is the heart: a non-root u with a child whose low[v] >= disc[u] is a cut vertex.
• On a back edge (v already seen and not the parent) we relax with disc[v], never low[v].
• The root uses the separate child-count rule on lines 19-20.

Complexity

We replace V separate connectivity checks with one DFS, going from O(V · (V + E)) down to linear O(V + E). The extra space is O(V) for the disc, low, and recursion stack.

When this pattern shows up

Practice