# What is the maximum number of cities that can be destroyed?

As a commander of an army battalion, you have to plan the attack on some enemy cities which are connected by road-network. Before starting the attack, you have information about all the cities and roads connecting them. You can start attack from any city but you must travel from one city to another via roads only. To prevent enemy re-enforcement and block transport through a city, you reach there, destroy it and burn it while leaving behind. This makes it impossible for you to return to a city (via any road) destroyed by you in past.

Given a list of all the roads (each connecting a pair of cities), you have to tell what is the maximum number of cities that can be destroyed by the strategy mentioned above.

If this is the list of road: (pairs x <---> y which denotes that there exists a direct road from city ‘x’ to city ‘y’)

1 <---> 2
1 <---> 11
2 <---> 3
3 <---> 11
4 <---> 5
4 <---> 11
4 <---> 12
5 <---> 6
5 <---> 7
6 <---> 7
8 <---> 9
8 <---> 10
8 <---> 12
9 <---> 12
9 <---> 10

Then what is the maximum number of cities that can be destroyed?

• Did you copy this posting from a programming contest? It's odd to list the number of cities as being variable and then giving a specific list. You should update the posting so that it is formatted as a specific question. May 1, 2015 at 11:14
• This problem is known as the longest path problem. Googling around probably will find some usable algorithm.
– Ivo
May 1, 2015 at 11:15
• @IvoBeckers Yes of course I know that, but I stake the riddles that others can advance acquaintance from it. May 1, 2015 at 12:38
• Why can't your battalion travel through a destroyed city? May 1, 2015 at 14:41
• @NoctisSkytower because it's on fire! If the supporters can't get through it then why should I be able to get through it? May 1, 2015 at 16:06

Ans:

The answer in this case is 9. A possible path is 8, 10, 9, 12, 4, 11, 3, 2, 1. More than 9 is not possible because 4 can only be travelled through once.

• Nice touch with the drawing. May 1, 2015 at 15:39

Each of the path segments connected to $4$ can be traversed to get to $4$: $(1\rightarrow2\rightarrow3\rightarrow11\rightarrow4)$, $(6\rightarrow7\rightarrow5\rightarrow4)$, $(8\rightarrow10\rightarrow9\rightarrow12\rightarrow4)$. But once you get to $4$, you can't go back, and thus can only destroy one segment after reaching $4$. The segment that should be untouched, to maximize destruction, is the smallest segment $(5,6,7)$.
Therefore, the remaining 9 cities can be destroyed, and no more. One possible path is $(1\rightarrow 2\rightarrow 3\rightarrow 11\rightarrow 4\rightarrow 12\rightarrow 9\rightarrow 10\rightarrow 8)$.