SPOJ : BANKROB STATEMENT NOT CLEAR

Question

I have recently started practicing graph theory problems. I recently encountered this problem : BANKROB

Even after having gone through the problem statement several times, I am unable to understand how the given output for the sample cases has been computed. I will be grateful to you, if you can please explain the sample test cases.

Answer 1

To understand the solutions, it helps to visualize the data that's depicted. (Of course, you'll have the computer program do this entirely differently.) Based on the input, the roads basically look like this:

    2 - 5 - 7
  /   /   \   \
1 - 3 - 6 - 8 - 10
  \   /   \   /
    4       9

To cut off all paths from 1-10, just remove the choke points at 5 and 6.

However, to cut off from 5-10 (assuming all the roads are bidirectional), you can't just remove 7 and 8 - the robbers can backtrack from 5-3-6-9-10. So you have to cut off 7, 8 and 9.

Thus, for the first example, there are 2 places to cut off, but in the second, there are 3.

Answer 2

I'll explain one.

The first line says the city has ten crossroads (nodes) and 14 roads (edges). This helps you set up the problem, but it's not really necessary because you can tell that from the remainder of the input.

The second line says the robbers' goal is to get from node 1 to node ten. (your goal is to stop them).

The third through 16th lines each represent one road (edge.) Note that there are 14 edges and ten nodes as predicted by line 1. This information lets you create a graph.

To capture the robbers you need block (delete) the fewest possible nodes to separate node one from node ten. As it turns out in this case deleting node five and six will do the trick, so the answer to the question is 2, the number of crossroads you need to delete.

Now how to compute this? Well that's what you are studying, right?