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.
↵
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.
