Attack Cities and Conquer

Computer Science Level 5

As Sheldor the conqueror, you're supposed to conquer the kingdom of Wonder-blunder-berg, which happens to be a collection of cities connected with roads.

Your first plan is to attack cities, which when blocked, splits the kingdom into parts that cannot communicate with each other.

For example,



In the above kingdom, the multicolored cities, when removed, disconnect the road network.

This is the Adjacency List of the road network of Wonderblunderberg showing which city has a direct road to which other city.

How many such vulnerable cities exist in the kingdom?

Clarification: A component is a maximal set of cities such that there is a walk between any two cities of the set. A vulnerable city is a city which when, along with its roads, removed, increases the number of components.

The title is just a title, it has nothing to do with the algorithm you'll need.

Image Credit: Wikimedia Zyqqh.

Problem Loading...

Note Loading...

Set Loading...