medium +25 pts

Articulation Points

Find all vertices whose removal disconnects an undirected graph.

An articulation point (or cut vertex) of an undirected graph is a vertex whose removal increases the number of connected components. (For a vertex with incident edges, removal also removes its edges.) Your task is to implement the function `articulation_points(n, edges)` that, given the number of vertices `n` (vertices are labeled `0` to `n-1`) and a list of undirected edges `edges` (each edge given as a tuple `(u, v)`), returns a list containing all articulation points of the graph. The list must be sorted in ascending order. If there are no articulation points, return an empty array. The graph may be disconnected. Isolated vertices (with no edges) and vertices of degree 1 can never be articulation points (removing a degree‑1 vertex does not disconnect the graph). Multiple edges between the same pair of vertices should be treated as a single edge (i.e., the graph is simple). You need to implement the function `articulation_points(n, edges)` where: - `n` is an integer, the number of vertices. - `edges` is a list of tuples, each `(u, v)` representing an undirected edge. Return a list of integers (the articulation points) in ascending order.

Constraints

Constraints: - `1 <= n <= 10^5` - `0 <= len(edges) <= 10^5` - Input graph may have multiple edges, but they should be treated as simple. - The graph may be disconnected. - Complexity requirement: O(n + m) time, O(n + m) space.

Example

>>> articulation_points(5, [(0,1), (1,2), (2,0), (1,3), (3,4)])
[1, 3]
>>> articulation_points(3, [(0,1), (1,2)])
[1]
>>> articulation_points(4, [(0,1), (1,2), (2,3)])
[1, 2]
>>> articulation_points(3, [(0,1), (1,2), (2,0)])
[]
25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about depth‑first search (DFS) and a `disc`/`low` array.
For every DFS tree edge (u,v) where v is a child, if `low[v] >= disc[u]`, then u is an articulation point (except possibly for the root).
For the root, it is an articulation point if it has more than one child in the DFS tree.
Handle multiple edges carefully: ignore duplicate edges when building the adjacency list to keep the graph simple.
Explore each connected component separately.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.