Articulation Points Sorted List

Problem

List all articulation points of an undirected graph in increasing order.

An articulation point is a node whose removal increases the number of connected components. Run a DFS with discovery times and low-link values: a non-root v qualifies when a child w has low[w] >= disc[v], and the root qualifies with more than one DFS child. edges is a list of [u, v] pairs.

Hint

Only tree children can expose an articulation, and the root is the special case.

Test cases

case 1

in: [3,[[0,1],[1,2]]]

expected: [1]

case 2

in: [3,[[0,1],[1,2],[2,0]]]

expected: []

case 3

in: [5,[[0,1],[1,2],[2,0],[1,3],[3,4]]]

expected: [1,3]

case 4

in: [4,[[0,1],[1,2],[2,3],[3,0]]]

expected: []

case 5

in: [1,[]]

expected: []

Starter codePython

def articulation_points_list(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor