Boxer's blog

By Boxer, 7 years ago,

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

 » 7 years ago, # | ← 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.
•  » » 7 years ago, # ^ |   0 Very nice idea and explanation , i don't really know that property about bridges.Thanks.
•  » » 5 years ago, # ^ |   0 How was "very similar" did you mean?
•  » » 5 years ago, # ^ |   +3 ffao I could not develop a similar claim for articulation vertices in query2. Could you please explain it in some detail ?
•  » » » 5 years ago, # ^ |   +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 years ago, # ^ | ← Rev. 5 →   +7 L.
•  » » 4 years ago, # ^ |   0 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, # ^ |   0 I am using the idea that you told but I get WA on 10th test case.
 » 5 years ago, # |   0 Where did you find official solutions, mate?? pl. share the link
 » 5 years ago, # |   0 Here is an easy to understand and short solution :- Link on Github
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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.