Give you an undirected graph with no guarantee of connectivity, Erase 2 edges to minimize the maximum connected block. You only need to output The size of the largest connected block.
How to solve it in less than O(N^2) Time Complexity ?
Sorry of my suck English :(
UPD: We have found an another O(N^2) Algorithm. We can check all edges, try to delete the edges that we are checking, and then use the Tarjan's algorithm (Tarjan, R. E. (1974). "A note on finding the bridges of a graph") for the remaining edges. Perhaps optimizing this algorithm can reduces time complexity.
Auto comment: topic has been updated by Inversentropir-36 (previous revision, new revision, compare).
You should check for all components of graph with DFS. It gives you amount of them and amount of vertexes. Then your idea is simple. Let's check how erasing each edge will impact on this component and store it somehow, for example : (a, b) <- a, b — amounts of vertexes from both sides of edge. Then "best" is gonna be erased. Then run it again. It gives us O(NlogN) if we use sort. Maybe it has better solution, but I don't see it now.
imzzy says your Solution isn't correct.
Because My idea isn't very simple.
First, Your solution can't count it in O(N) or O(N log N). It's O(N^2) to get all information.
Although use sort, It's Still O(N^2).
I may have misunderstood you, but I think the solution isn't looks right
Auto comment: topic has been updated by Inversentropir-36 (previous revision, new revision, compare).
Should be equivalent to finding spqr tree ie tree formed from triconnected components and seeing best point to split the tree accounting for nodes in more than one group somehow. Don't know how it works but the website linked claims it can be done in linear time, so I would suggest learning that algorithm and going from there.
Thank you for your suggestion!
If this algorithm works, Maybe I will introduce it to CNOI :)