Articulation Split Counts

Problem

For every articulation point, report how many components remain after deleting it.

Compute the baseline component count of the undirected graph, then for each node v count the components of the subgraph induced by all nodes except v. Node v qualifies when that count exceeds the baseline. Return [v, count] pairs in increasing v order; return an empty list when the graph has no articulation points.

Hint

Compare the component count without v to the count of the original graph; increases reveal articulation points.

Test cases

case 1

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

expected: [[2,2]]

case 2

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

expected: [[1,2],[2,2],[3,2]]

case 3

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

expected: [[1,2]]

case 4

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

expected: []

case 5

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

expected: []

Starter codePython

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

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