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