Help in this question
There are N cities that are connected by N-1 roads.K cities have bus terminals and other N-k cities have bus stops. A bus terminus is a designated place where a bus starts or ends its scheduled route.
A bus should start from a terminal and must end its journey at another terminal visiting any city at most once. A city is crowded if there is a bus service in the city where one or more than one bus visits it along any route. You are required to simulate the routes for the buses so that the maximum number of cities is crowded. You can assume there is a number of buses ready for service from each terminus.
Input
First line: Two space-separated integers N and K
Next N-1 lines: Two integers u and v that denote city and city is connected by a road
Next line: K integers denoting the cities that have a bus terminal
Input:
5 3
1 2
1 3
2 4
2 5
1 4 5
Output:4
Explanation:
It is possible to simulate a bus route starting from terminus 1 to terminus 4 or 5 thereby making city 2, a crowded city. But it is impossible to make city 3 crowded.
I was using connected components of the tree given above of 1,2, 1,3, 2,4,2,5 and storing it in an ArrayList and then taking the maximum size of the ArrayList that I have found and the one that was given 1 4 5.It is not as efficient.Can anyone code it in efficient way?
A bus should start from a terminal and must end its journey at another terminal visiting any city at most once. A city is crowded if there is a bus service in the city where one or more than one bus visits it along any route. You are required to simulate the routes for the buses so that the maximum number of cities is crowded. You can assume there is a number of buses ready for service from each terminus.
Input
First line: Two space-separated integers N and K
Next N-1 lines: Two integers u and v that denote city and city is connected by a road
Next line: K integers denoting the cities that have a bus terminal
Input:
5 3
1 2
1 3
2 4
2 5
1 4 5
Output:4
Explanation:
It is possible to simulate a bus route starting from terminus 1 to terminus 4 or 5 thereby making city 2, a crowded city. But it is impossible to make city 3 crowded.
I was using connected components of the tree given above of 1,2, 1,3, 2,4,2,5 and storing it in an ArrayList and then taking the maximum size of the ArrayList that I have found and the one that was given 1 4 5.It is not as efficient.Can anyone code it in efficient way?
| Can anyone code it in efficient way? |
Yes, done.
Oh, you want the code? Write it yourself since this is a code challenge.
Topic archived. No new replies allowed.