Imagine the following real life setting of the problem the so-called Dominating Set Problem.
Let's say there are some cities connected by roads. There is only at most one road between any two cities
(so some cities are not connected directly). A company which sells smartphones would like to take over as much
of the market as possible. To do that they would have to own a store in some cities, so that for every
city there either is a store in this city or in a neighboring one. Of course, the company wants to spend as
little money as possible so the number of cities in which they will build a store should be minimal.
Having a map with cities and roads, the programmer's task is to determine in which cities the company
should build a store.
All known exact solutions to this problem will take more or less forever to calculate the answer for a large number of cities. One way to approach the problem would be to plow through (almost) all possible sets of cities and check whether they constitute a valid solution – but this would take very long. The programmer may, however, skip most of them, still getting a good result and cutting calculation time dramatically.
The first line contains the number of cities n (n < 20000). After that there comes a
description of the road connections of each city starting from city number 1 to city number n. Each city is described
in two lines. In the first one, there is only the number of the city's neighbours. In the second one, there is a list of its neighbours.
The first line should contain one number - the number of cities in which the company should build stores.
The second line should contain a list of those cities.
For each test, the programmer receives as many points as the number of cities in
which stores needed to be built, provided that the solution fulfills the requirements.
Thus, the smaller the score is, the better the program.
3 5 6
Illustration of the input
Score for the output:
2 4 7
Comment to the example:
As you might have noticed, the output above is not the optimal solution.
Two cities are enough to fulfill the requirements: city 5 and city 6.