DSA interview question

Articulation Points in a Graph

Hard · Data structures · Topics: graph, dfs, articulation point

The problem

In a road network, some intersections are single points of failure: if an intersection closes, part of the city is cut off. These vertices are articulation points (cut vertices). Tarjan's DFS with discovery times and low-links finds them all in one pass:

A non-root vertex u is a cut vertex if some DFS child v has low[v] ≥ tin[u], meaning v's subtree can't reach above u without going through u.
The root is a cut vertex if it has two or more DFS children.

Example: 5 vertices, edges 0-1, 1-2, 2-0, 1-3, 3-4 → [1, 3].

Function signature

vector<int> articulationPoints(int V, const vector<pair<int, int>>& edges);  // sorted, or {-1} if none

Test cases

Input `(V, edges)`	Output	Explanation
`(5, [[0,1],[1,2],[2,0],[1,3],[3,4]])`	`[1, 3]`	1 separates {3, 4}; 3 separates {4}
`(4, [[0,1],[1,2],[2,3]])`	`[1, 2]`	Interior vertices of a path
`(5, [[0,1],[0,2],[0,3],[0,4]])`	`[0]`	The centre of a star
`(3, [[0,1],[1,2],[2,0]])`	`[-1]`	A cycle has none
`(2, [[0,1]])`	`[-1]`

(Confirm: the graph is undirected and simple; it may be disconnected; return [−1] when there are no articulation points.)

How interviewers phrase it

"Find all articulation points in an undirected graph: vertices whose removal increases the number of connected components; return [−1] if there are none" (GeeksforGeeks "Articulation Point").

Clarifying questions to ask

Can the graph be disconnected? (Yes, so treat every DFS tree separately.)
What output format? (Sorted, or [−1] when there are none.)
Parallel edges? (Assume a simple graph.)

Follow-ups to expect

"Why ≥ here but > for bridges?"
"Why is the root special?"
"Why count DFS children, not neighbours?"
"What are biconnected components?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview