SRM 686, D2, 250-Pointer (TreeAndVertex)

James S. Plank

Sun Oct 9 18:51:57 EDT 2016
If you remove vertex i, and there are c edges coming out of i, then you will be left with c components. So this problem is a straightforward matter of counting the number of edges coming out of each vertex.

Maintain a vector E so that E[i] contains the number of edges coming out of node i. Run through each edge, and add one to the E value of the nodes on each side of the edge.

Then calculate the maximum.


Solution