Articulation Point in Graph

Given an undirected graph with V vertices (0 .. V-1) and edges edges (no self-loops or duplicate edges), return all articulation points (cut vertices) — vertices whose removal increases the number of connected components — in ascending order.

Hints

· Stuck? Reveal one nudge at a time.

An articulation point's removal increases the number of connected components.

DFS with disc[u] and low[u]; a non-root u is a cut vertex if some child has low[v] >= disc[u].

The DFS root is a cut vertex iff it has two or more DFS children.

Common doubts

A cut vertex only needs the child unable to reach ABOVE u (it may reach u itself); a bridge needs the child unable to reach even u — a stricter condition.

The root has no parent, so the child condition doesn't apply; it's a cut vertex only when it joins two or more separate DFS subtrees.

Yes — a vertex joining two cycles is a cut vertex, but the edges around it are on cycles, so none are bridges.

Interview follow-ups

· What an interviewer asks next.

Articulation points are exactly the vertices shared by two or more biconnected components.

Track the stack of edges during DFS and pop a biconnected component whenever the ≥ condition fires.

Fun facts

A graph with no articulation points is '2-vertex-connected' (biconnected).
The same disc/low DFS finds SCCs, bridges, and articulation points — Tarjan's Swiss-army traversal.

Asked at

GoogleAmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: V = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]
Output: [1, 3]
Removing 1 splits the triangle from the tail; removing 3 isolates 4.

Example 2

Input: V = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
Output: []
A single cycle has no cut vertices.

Constraints

- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - no self-loops or duplicate edges

An articulation point is a vertex the graph can't afford to lose without falling apart. Tarjan's algorithm finds them in one DFS with the same disc/low machinery as bridges:

disc[u] — discovery time; low[u] — earliest discovery time reachable from u's subtree via one back edge.
A non-root u is an articulation point iff some child v has low[v] ≥ disc[u]: v's subtree cannot reach above u, so removing u cuts it off. (Note ≥, not the strict > used for bridges.)
The root of the DFS tree is an articulation point iff it has two or more DFS children — removing it separates them.

O(V + E). The brute force removes each vertex and recounts components (O(V · (V + E))).

Prerequisites

Before you start

· Concepts used directly in the solution.

disc & low. the DFS-timing pair.

≥ vs >. articulation uses ≥; bridges use >.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“What's an articulation point?”

A vertex whose removal increases the number of components.

“Output order?”

Ascending.

The ideal opening — say it like this

I DFS with disc/low; a non-root u is a cut vertex if some child's low is ≥ disc[u], and the root is one if it has two or more DFS children.

The ≥ (vs the bridge's strict >) captures that the child can reach back only as high as u, not above.

Understand the problem

Worked example — V = 5, edges [[0,1],[1,2],[2,0],[1,3],[3,4]]

1 connects the triangle {0,1,2} to the tail 3-4 -> removing 1 splits them -> articulation
3 connects to leaf 4 -> removing 3 isolates 4 -> articulation
answer = [1, 3]

Key observations

1Aha

Non-root: low[child] ≥ disc[u]

The child subtree can't bypass u.

2Aha

Root: two or more DFS children

It joins otherwise-separate subtrees.

3Aha

≥ vs > distinguishes it from bridges

Articulation points use the non-strict test.

Brute force vs optimal

	Remove each vertex	Tarjan (disc/low)
Idea	recount components without it	one DFS with low-links
Time	O(V·(V+E))	O(V+E)
Condition	component count increases	low[v] ≥ disc[u] (or root child-count)

Both find the same cut vertices. Full code is in the Approaches selector below.

Summary

Key takeaway

An articulation point's removal disconnects the graph. Tarjan: a non-root u is one iff a child has low[v] ≥ disc[u]; the root iff it has ≥ 2 DFS children. O(V+E).

non-root u: some child v with low[v] >= disc[u]
root u: DFS child count >= 2