How to connect villages with a specific amount of roads?


Joined
May 29, 2022
Messages
1
Reaction score
0
Let's say the road network of your country is destroyed and you are asked to rebuild it. You have N villages(numbered from 1 to N) and M roads that weren't destroyed(every road is two-way road and there is no other road that connects the same 2 villages, ex village 1 and 2 are connected only by road 1). Not every village can connect with every other village, but those who do, form a "group".The government offers to build K new roads. If we know the number N of villages, the number M of the old roads and which two villages are connected by each road, and also the number K of the new roads the government wants to build, how to find the least possible number of independent groups that can remain after the construction of the new roads.

I have an example below. Let's say we have 7 villages(N = 7, the blue circles) and 2 old roads that connect 1-2 and 5-6(M = 2, the blue arrows). 1-2 and 5-6 form two separated groups. Then we want to build 2 new roads(K = 2, the red arrows) and so we decide to connect villages 3,4,7 who where alone. In the end we have 3 separated groups {1,2}, {5,6}, {3,4,7}. This is also the least possible number of independent groups that can remain after the construction of the new roads.
 

Attachments

  • Screenshot 2022-05-29 at 6.26.25 PM.png
    Screenshot 2022-05-29 at 6.26.25 PM.png
    159.6 KB · Views: 3
Ad

Advertisements


Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top