Boxer's blog

SPOJ POLQUERY
By Boxer, 12 years ago, In English

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.

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

Comments Comments (7)
| Write comment?
»
12 years ago, hide # |
← Rev. 2  
Vote: I like it +9 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    Thanks.

    → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    How was "very similar" did you mean?

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

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

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

      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.

      → Reply
  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    → Reply