Monday, February 17, 2014

traval maximum unvisited cities each day.

Q:
 Input (arr, k )
Output:a list of ending cities till traversal.

背景描述:

Given n cities, indexed from 0 to n-1, we have an array arr, of size n, where A[i] =j, means that there is a direct road between city i and j. there are n-1 roads, all cities are connected.
 for example :  we have 7 cities
                           3                   5
                           |                   | 
                           |                   |
                           |                   |
0 ------------------1 -------------- 2 ----------------4 ----------6
array[ 0 ]  = 1
array[ 1]  = 2
array[ 2 ]  =4
array[ 3 ]  = 1
array[ 4 ]  =6
array[ 5 ]  =2
array[ 6 ]  = 4    

Starting from city  k , each day we visit maximum number of unvisited cities, , but we traval back on the same day.

Print the last city that you visited each day, (ending city) , untill all cities are marked visited.
For example:   k = 2, 
one day 1 , you can visit 3 unvisited cities,   2-1-0(ending city is 0),  or 2-1-3,  or 2 - 4- 6.
so, our final output could be :
0   6     5 3
also, it could be   0 6 3 5,   or  6 0 3 5   or  6 0 5 3,  or 3 6 1 5  or 3 6 5 1

O(n) space &  time

A:





No comments:

Post a Comment