How to solve this Graphical problem?

Правка en3, от A1p36th, 2020-11-18 11:08:32

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 algorithm for the remaining edges. Perhaps optimizing this algorithm can reduces time complexity.

Теги #graph theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский A1p36th 2020-11-19 07:25:35 69
en3 Английский A1p36th 2020-11-18 11:08:32 247 UPdate for our new algorithm.
en2 Английский A1p36th 2020-11-16 08:56:02 2 Tiny change: 'cted block。\n\nHow to' -> 'cted block.\n\nHow to'
en1 Английский A1p36th 2020-11-16 08:53:14 307 Initial revision (published)