- 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.
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.
