Pages

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?

Courtesy : Aakash rao NS

2 comments:

chan said...

is it N.

pathankhan salman said...

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.