GrandmomPanties's blog

Path finding!
By GrandmomPanties, history, 8 years ago, In English

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

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

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

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

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

    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?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it +5 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        → Reply