POJ 3177 - Redundant Paths
Problem : Add the minimum number of edges to make an undirected (connected) graph become edge-bi-connected graph.
Solution : Merge the graph depending on the edge-bi-connected set of graph, and it becomes the undirected acyclic graph. Find the number of vertices which has exactly one degree. The answer is (that number+1) div 2.
Proof :
1. Let u to be one of the vertices which has only one degree. If an added edge not connect it, it will has only one path to its neighbour. Since an edge connects at most two such vertices, thus the answer is at least (the number+1) div 2.
2. There is actually an method to get the request with (the number+1) div 2 edges.
	A. The graph will not has the situation that there is only one vertice with one degree.
	B. If the number is 2, connect the 2 end points and meet the request.
	C. If the number is 3, connect 2 such vertices to another vertice and meet the request.
	D. The number is >3. For each vertice, there must be at most 1 another 1-degree vertice such that when connect them, the number of 1-degree vertices in merged graph (by edge-bi-connected set created by that edge) decreases by 1. Otherwise decreases by 2.
[]