Articulation Points Graph Algorithm using torjan’s algorithm Cut Vertices
Facts:
 Root is articulation point iff it has more than one child
 Any other vertex v is an articulation point iff v has some child w such that Low(w) ≥ Num(v)

 I.e., is there a child w of v that cannot reach a vertex visited before v?
 If yes, then removing v will disconnect w (and v is an articulation point)
 Can compute Num(v) and Low(v) in O(E+V) time
Algorithm:
 From any vertex v, perform DFS and number vertice as they are visited
 Num(v) is the visit number
 Let Low(v) = lowestnumbered vertex reachable from v using 0 or more spanning tree edges and then at most one back edge

 Low(v) = minimum of
 Num(v)
 Lowest Num(w) among all back edges (v,w)
 Lowest Low(w) among all tree edges (v,w)
 Apply DFS on a graph. Get the DFS tree.
 A node which is visited earlier is a “parent” of those nodes which are reached by it and visited later.
 If any child of a node does not have a path to any of the ancestors of its parent, it means that removing this node would make this child disjoint from the graph.
 There is an exception: the root of the tree. If it has more than one child, then it is an articulation point, otherwise not.
Latest Source Code:
Github: GraphCutVertices.java
Output:
 T      T  T T     T   T    T   T T T   T T       T   T    T  T  Articulation Points: [3, 1]