# 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. – LeppyR64 May 1 '15 at 11:14
• This problem is known as the longest path problem. Googling around probably will find some usable algorithm. – Ivo Beckers May 1 '15 at 11:15
• @IvoBeckers Yes of course I know that, but I stake the riddles that others can advance acquaintance from it. – Mox Shah May 1 '15 at 12:38
• Why can't your battalion travel through a destroyed city? – Noctis Skytower May 1 '15 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? – LeppyR64 May 1 '15 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. – Michael McGriff May 1 '15 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)$.