Inversentropir-36's blog

By Inversentropir-36, history, 4 years ago, In English

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.

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Inversentropir-36 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Inversentropir-36 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you for your suggestion!

    If this algorithm works, Maybe I will introduce it to CNOI :)