Graph Theory37 sections · 1633 units
Open in Course

Problem - Finding Articulation Points

(Critical vertices in network)

Problem: Given an undirected graph, find all articulation points (cut vertices). Input: adjacency list or edge list. Output: list of vertices whose removal disconnects the graph or isolates parts of it. This is the vertex version of the bridge problem. You will use Tarjan's algorithm with a slight modification to detect articulation points instead of bridges.

The condition changes from low[v] > disc[u] to low[v] >= disc[u].