Ninjas’ Vacation

The basic idea is to generate all permutations in which cities can be visited. For each permutation, we create a map to store the adjacent cities. If a city is not present in the map then the path will not be valid, else valid.

Example: 

Let a permutation be: 1 3 2 4

We create a map and insert the first element of permutation initially into it. Map : {1}

We now add all adjacent cities of 1 into the map, so the map becomes: {1, 2, 3, 4}

We move to the next element in the permutation, i.e., 3 which is present in the map and add its adjacent cities into the map. 

As all the cities are present in the map, so the permutation will be valid.
 

Now, let a permutation be: 1 4 3 2

Similarly, we will create a map and insert 1 into the map, so the map biomes: {1}

We will insert cities adjacent to 1 into the map, so the map now becomes: {1, 2, 3}

We move to the next element in the permutation, i.e., 4 which is not present in the map.

The permutation becomes invalid as 4 was not present in the map.
 

    We can do this for all the permutations to count the number of valid ways.
 

Here is the algorithm :

1. Create a graph (say, ‘GRAPH’) using the ‘CITIES’ array in the form of an adjacency list. (An array of lists in which ‘arr[i]’ represents the lists of vertices adjacent to the ‘ith’ vertex).
2. Push the edges in the ‘GRAPH’.
3. Create an array (say, ‘ARR’) of size ‘N’ which will be used to store the permutations and initialize it from 0 to ‘N’.
4. Create a variable (say, ‘RES’) that will store the number of ways and initialize it with 0.
5. Call the ‘HELPER’ function which will generate all the permutations of array ‘ARR’.

HELPER(‘GRAPH’, ‘ARR’, ‘SI’, ‘EI, ‘RES’)
 

1. Base case:
   • If ‘SI’ is equal ‘EI’.
     1. Call the ‘CALC’ function which will check for the validity of the path and update the value of ‘RES’ by adding the result of the function.
2. Run a loop from ‘SI’ to ‘EI’ (say, iterator ‘i’) that will generate all the permutations of the array.
   • Swap ‘ARR[i]’ and ‘ARR[SI]’
   • Call the function recursively to generate other permutations.
   • Backtrack by again swapping ‘ARR[i]’ and ‘ARR[SI]’.
      

CALC(‘GRAPH’, ‘ARR’, ‘N’)

1. Create a map (say, ‘STORE’) that will store the adjacent cities and insert ‘ARR[0]’ into it.
2. Run a loop from 0 to ‘N’ (say, iterator ‘i’) to traverse the cities present in the array.
   • Check if ‘ARR[i]’ is not present in ‘STORE’.
     • Return 0.
   • Insert all the cities which are adjacent to ‘ARR[i]’ into the map.
3. Return 1.

O(N!*(N^2)), where ‘N’ is the number of cities.
 

We generate all permutations in which cities can be visited which take N! of time and for each permutation, we traverse it and check whether it’s a valid permutation or not. We traverse all the elements of a permutation and for each element, we traverse its adjacent cities which can up to ‘N’ - 1. Therefore, the overall time complexity will be O(N!*(N^2)).

O(N + M), where ‘N’ is the number of cities and ‘M’ is the number of roads.

For each city, we store its adjacent cities, therefore storing the cities in the form of a graph will require O(N + M) space. We also use an array of size ‘N’ to store the permutation. We use a map also to store the adjacent cities. The recursive stack to generate permutation can have maximum ‘N’ calls. Therefore, the overall space complexity will be O(N + M).