Cuts

This option finds the Cut Vertices ( AKA Articulation Points ) in an undirected graph. These are the vertices that, if any one is removed, then the graph is split into an increased number of unconnected components.

Input

format

The first line specifies the calculation required. It must contain

format cuts

Links

Column	Description
1	l for link
2	node name
3	node name

Algorithm

Finds cut vertices using the Tarjan algorithm. https://en.wikipedia.org/wiki/Biconnected_component

Performance

This code can handle, without exhausting the default stack size, a graph with 4,720 vertices 13,722 edges from https://dyngraphlab.github.io/ ( 3elt.graph.seq.txt ) in 27 seconds.