Graph  7. Articulation Points
#7. Articulation Points (Cut Vertex)
What is Articulation Point?
Articulation points are the nodes in a graph, whose removal increases the number of connected components
How to find articulation points?
 If an edge (v, w) is a bridge, then either v or w is an articulation point. But articulation points can exist without any bridges.
 If id(e.from) == lowlink(e.to), that means there is a cycle
 A cycle must be a connected component, and e.from is the starting node of the cycle, which indicates it’s an articulation point.
 Except the starting node has no
outgoing
edges. Or only 1 outgoing edge, which is part of the cycle.
 Except the starting node has no
 So an articulation point must have 2 or more outgoing edges.
 If an edge (v, w) is a bridge, then either v or w is an articulation point. But articulation points can exist without any bridges.
[Notes] The “outgoing” here is a logical outgoing, it does not mean the outgoing edge in directed graph, since the whole problem is on an undirected graph. It really means the edges connected to the node.
Python Find Articulation Points

