Boxer's blog

By Boxer, 7 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

»
7 years ago, # |
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.

  • »
    »
    7 years ago, # ^ |
      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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How was "very similar" did you mean?

  • »
    »
    5 years ago, # ^ |
      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 ?

    • »
      »
      »
      5 years ago, # ^ |
        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.

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

    can anyone tell me that after query of type 1 do we keep the baracades on the road that we didn't use and also if we remove c does this mean that c is removed permanenetly or just for that query it is not considered. I'm confused and i don't want to see the solution or read anything about the solution .So if you could just answer my query. Thanks in advance.

  • »
    »
    2 years ago, # ^ |
      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.

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

Where did you find official solutions, mate?? pl. share the link

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

Here is an easy to understand and short solution :- Link on Github

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My point of confusion. In Line 61: if(desc(a, v) == desc(b, v)) puts("da"); why just desc of v ; a,b can be ancestor of u as well.