407133: GYM102697 104 Trans Europe Express

Trans Europe Express

You're traveling on the Trans Europe Express, which consists of many train lines between cities. You want to know how many cities you can reach from a given start city, traveling only on the Trans Europe Express.

For example, if you started in City A, and the Trans Europe Express had train lines between City A and City B, City B and City C, and City D and City E, you could travel to City B or City C, but not to City D or City E.

For problems like these, you can use the graph theory algorithm Breath-First Search (BFS). The algorithm is described below in pseudocode:

1. Define an empty list of cities. Add the start city to the list.

2. Select the first city in the list of cities, and remove it from the list.

3. Mark the selected city as visited

4. For any edges that connect the selected city to another city, add the other city to the list of cities, if the city has not been visited yet

5. If the list of cities is not empty, repeat steps 2-4.

Then, the answer would be the number of cities that have been visited.

The first line of input contains two space-separated positive integers $$$n$$$ and $$$m$$$: the number of cities, and the number of train lines on the Trans Europe Express. The next line of input contains a single string $$$s$$$, representing the start city. The next $$$m$$$ lines contain one of the train lines of the Trans-Europe Express: two space-separated strings: the cities that the train lines connect. The train lines can be traveled in both directions.

Output a single integer $$$c$$$: the number of cities that you can visit by traveling only on the Trans Europe Express train lines.

8 7
Dusseldorf
Dusseldorf Frankfurt
Frankfurt Berlin
Berlin Hamburg
Berlin Prague
Vienna Salzburg
Salzburg Zurich
Zurich Vienna

5

3 2
Syracuse
Syracuse Utica
Syracuse Rochester

3

Given that the pseudocode of the algorithm treats the cities as numbers rather than names, you should first map each city name to a number, before running the BFS algorithm.