Courtesy : Aakash rao NS
Thursday, July 26, 2012
City-roads
There is a country consisting of N cities, just built. So, now you must build roads for the cities. Each road is a two-way path joining two cities. The way it works is, in one turn, you must choose two cities, and if there is no road between them, build a road, else, leave it as it is. What is the estimated number of turns required to build the roads such that there is a way from every city to every other city?
Subscribe to:
Post Comments (Atom)
2 comments:
is it N.
Minimum number of roads required to make the city connected itself is N-1. So, N is on a lower end, and even intuitively, it can't be the expected value. Anyways, you can just discuss your approach here if you want.
Post a Comment