Problem: In an imaginary world, there are N cities governed by K countries. Some of the cities have direct connection between each other and some do not. Moreover, territorial integrity is not an important issue for the countries.
A person named Luke, who lives in one of the cities, is not happy with any of these regimes in the whole world.
He/She plans to organize a group of people in arbitrary M cities (each of the pairs in these cities can be reached by only using the paths between these M many cities, so it has territorial integrity), to start a riot and to found his/her own kingdom with these M cities included. The problem is that the more number of distinct neighbors (number if countries that are connected to the M many cities) that the new kingdom have, the more threats are present for the new country. Thus, Luke wants the number of distinct neighbors as small as possible.
(a) Given the cities, their direct connections (if there are any), their country information, and the number M can you find the optimal set of cities that this new kingdom should be founded? How many number of distinct neighbors does this city have?
Input Format: The first line includes number of cities N and the second line indicates total number of connections E between these cities. The third line contains the number M. The next V lines have 2 numbers indicating the city id and the kingdom id which rules the city. The format is: ”city id kingdom id”. The next E lines indicate the cities that are connected with each other directly. The format is: ”city 1 id city 2 id”.
1 <= N, M, K <= 1000000
(Note: The graph is undirected & unweighted)
I’m not able to think of even a sub-optimal solution. Can someone please help?