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

Path finding!
Автор GrandmomPanties, история, 8 лет назад, По-английски

I have a problem and today I want to ask if this question have an answer or not! We have a graph and Jafar and Omidaz are at nodes x and y, each time Kodser destroys an edge and asks is there a path between Omidaz and Jafar or not! If the answer was negative Kodser puts the edge back and it doesn't destroy, at the end Shakheshoon want's to know how many edges are destroyed! nodes < 3e6, questions < 3e6

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

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

A little hint: try to process queries from the end and use dsu.

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

    This is offline and I think this problem wants an online solution because if the action destroys all the paths then we don't do that! Does your solution handle this?

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

    This doesn't work because If the answer was negative Kodser puts the edge back and it doesn't destroy. Queries must be processed in the given order.

    Example you have graph here:

    1
| 
2--3
| /
4

    Queries are 1 2, 2 3. Answer will be false true. True is because we replace edge 1 2. But your way going backward when we add in query 2 3 we get answer false.

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

      Well, I do not understand your example :) Starting from the end we have something like (suppose we are seeking for the path between 1 and 4 and those vertices are fixed)

      1

      2 3

      |/

      4

      (Sorry for this graph example, my iPad doesn't let me format that properly)

      First we try to add 2 3. Since 2 and 3 are already connected, deleting it makes nothing wrong -> the answer is true 1 2 is processed in a different way: 1 and 2 aren't connected, so we merge their components via dsu and set the answer for this edge to false. This results into false true :)

      Or did I get your idea wrong?

      EDIT: you were right. FeelsBadMan

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

        When you process backwards, you have to remove all the queried edges first and add them in reverse, right? When you try to add 2 3, your graph will be 

        1

2--3
| /
4

        Because 1 and 4 are in disjoint components you will mark answer as false, right? Maybe I have misunderstood your algorithm.

        → Ответить