Блог пользователя Boxer

SPOJ POLQUERY
Автор Boxer, 10 лет назад, По-английски

Hi everyone , i'm trying to solve SPOJ POLQUERY from COCI 2006 (Croatian Olympiad in Informatics) but i don't understand oficial solutions. Can somebody explain me ideas in order to solve this challenger problem.

Thanks in Advance.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

If a road connecting G1 and G2 disconnects two vertices A and B, that means the number of connected components has increased. By definition, this means the road is a bridge.

What may not be obvious is the inverse: if G1-G2 is a bridge, this means that if any path from A to B goes through G1-G2, then all paths from A to B use the G1-G2 road. In other words, a necessary and sufficient condition for the path to be blocked is that G1-G2 is a bridge and is used in at least one path from A-B. So the algorithm is simply:

  • If G1-G2 is not a bridge, the answer is "da".
  • Find any path from A to B
  • If that path uses G1-G2, the answer is "ne". Otherwise, the answer is "da".

It's still not clear how to find the paths. The trick is to consider only a spanning tree of the graph (the DFS tree, for example). In that case there is only a single path between any pair of vertices, and it's easy to check if G1-G2 belongs to it.

Query 2 is very similar.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Very nice idea and explanation , i don't really know that property about bridges.

    Thanks.

    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How was "very similar" did you mean?

    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    ffao I could not develop a similar claim for articulation vertices in query2. Could you please explain it in some detail ?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      I am very weak in this area so I may be wrong. Please feel free to point out any mistakes.

      For articulation vertices, they split the graph into biconnected components. If you create a graph of biconnected components as well as articulation vertices, it will look like a tree. Then you can find out, first if the deleted node is an articulation vertex, AND if path from bi-component of A to bi-component of B in this tree passes through the deleted node. If both are true then A is disconnected from B.

      → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I am using the idea that you told but I get WA on 10th test case.

    → Ответить