AlgoViz
HomeGraphs

Articulation point in graph

Hard

The same low-link test, one comparison looser

Problem

Find all articulation points (nodes whose removal disconnects the graph).

In simple words

A node is critical if removing it leaves some part unable to reach the rest.

The idea

A non-root vertex is an articulation point when some child's low-link is at least its own discovery time — meaning that subtree cannot bypass it. The root is special: it qualifies only if it has more than one DFS child.

The trick

  • Condition: low[child] >= disc[node], with >= rather than >.
  • The root needs two or more DFS children.
  • Same single DFS as bridges.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — graph Values: 0.

1/2
Optimal
timeO(V+E)spaceO(V)
1DFS with disc/low times2node is articulation if a child's low >= its disc (root: 2+ children)

Input

array
[0]

Output

answer
—

Check yourself

2 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
graph
Output:
list of cut vertices

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.