Computer Science 2400, Spring 2009
Programming Assignment #2b
Assigned: April 9, 2009
Due: April 23, 2009
Weight: 7%

To your main program for Assignment #2a, add the capability to perform the
following tasks.  As before, allow all tasks to be performed until the
user wishes to quit.

1.  Determine if the graph has any elementary cycles of length 3 or more.
An elementary cycle is a cycle in which the only repeated vertices are the
end vertices of a cycle.  a, b, c, a is an elementary cycle if there are
edges from a to b, b to c, and c to a, respectively.

2.  Determine the articulation points of the graph.  An articulation point
is a vertex such that the graph will become disconnected if the vertex and
its associated edges are removed from the graph.  Display the articulation
points of the graph.  If the graph has no articulation points, inform the
user.  Otherwise, display the vertices to the user.  If the graph is 
already disconnected, inform the user.

Why are articulation points important?  This is discussed in the Sedgewick
book on graph algorithms.  Suppose the vertices represent airports.
If an airport has inclement weather, we should be able to find alternate
routes to different cities.  For example, we should be able to go from New
York to San Francisco even if Chicago had a blizzard by flying via Denver.

3.  Determine the "critical" articulation point of the graph.  If the
graph has no articulation points, inform the user.  Otherwise,
the critical articulation point will be the articulation point with
the highest degree.  If there is a tie, the critical articulation point will
be the articulation point with the smallest size for its largest connected
component.  Otherwise (if there still is a tie), select a random articulation
point.

Sample Graph File Format:
9
Nashville
Chicago
Dallas
Los Angeles
Cleveland
New Orleans
Raleigh
Washington
Orlando
10
Chicago,Los Angeles
Dallas,Los Angeles
Nashville,Chicago
Nashville,Dallas
Cleveland,Nashville
Nashville,New Orleans
New Orleans,Raleigh
Raleigh,Cleveland
Raleigh,Washington
Raleigh,Orlando

The first line in the file denotes the number of vertices in the graph.  Call
this number n.  The next n lines in the file are the names of the vertices,
one per line.  The next line denotes the number of edges in the graph.  Call
this number m.  The next m lines in the file are the edges, with the endpoints
as names and separated by a comma.  You can assume that the graph is undirected.