There are some villages near a city in India that have yet to be connected to the city via road. Some villages are connected to each other via road and some aren’t. A village is said to be connected to the city if one can travel from that village to the city via any road. The cost of making a road between a city and a village and that of between a village and another village is the same and equal to 1 unit. Find the minimum cost the government must bear in order to connect all the villages to the city. Input: N: number of villages. Matrix: M[N+1][N+1] where 0 to N-1 indexes represents a village and the Nth index represents a city. M[x][y] = M[y][x] = 1 if there is a road between x and y.
