Last Updated: 3 Nov, 2021

Minimum walk

Moderate

Asked in companies

Solve now

Problem statement

There are ‘N’ cities in the Ninja world that are connected via ‘M’ bi-directional roads. Alice wants to take a tour in the Ninja world, but she doesn’t have so much time, so she chooses any city as a source, visits some cities, and gets back to where she started. In her journey, she doesn’t walk through any road more than once.

Your task is to find the minimum possible distance she needs to walk such that she ends in the same city where she started and doesn’t walk any road more than once. If no such path is found, return -1.

Note :-

Any pair of cities (x, y) have at most one road connecting them directly.
A city ‘x’ is reachable by any other city ‘y’ via some group of roads.
In input data, cities are numbered from [0, 1, ……. N-1].

Input Format:

The first line contains ‘T’, denoting the number of tests.
For each Test :
    The first line contains two integers, ‘N’ and ‘M’, denoting the number of cities and roads, respectively.
    Next ‘M’ lines contain two integers (x[i], y[i]), denoting a bi-directional road between city ‘x[i]’ and city ‘y[i]’.

Output Format:

For each test, print an integer, denoting the minimum distance needed to complete the tour at the starting point, walking any road at most once.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints -

1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^3
0 <= ‘M’ <= min(10^3 , N*(N-1)/2 )
0 <= x[i], y[i] < N  i ∈  (1,M)
Note - Sum of ‘N’ and Sum of ‘M’ over all test cases does not exceed 10^3.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach: Take the given network as a connected graph with ‘N’ vertices and ‘M’ edges.
Let’s assume that the given graph is a rooted tree (with loops), and each loop must have the root node in its path. For such cases, loops can be easily detected with BFS / DFS traversal. But the lengths of loops are also needed, so BFS is preferred.
While traversing the tree, if any node ‘x’ is visited more than once, then it’s in a loop, and the length of the loop will be [previous distance of node ‘x’ from root + current distance of ‘x’ from root].
Using the above assumption, we can find lengths of all loops passing through the ‘root’ node. Now, we take each vertex of the graph as the root node one by one and run a BFS traversal.

Algorithm:

Convert given connections / roads into graph representation.
Create a variable ‘ans’ and initialize with infinite.
Iterate a for loop from i = ‘0’ to ‘N-1’ to assume i-th node as root.
Make source / root vertex = i .
Run BFS.
Maintain two arrays dist[] and parent[], each of length ‘N’.
‘dist’ will store distances of all nodes from root and ‘parent’ will keep track of parent node for each node, in the assumed tree.
Initialize ‘dist’ with Infinite value and ‘parent’ with -1 at all indices.
Here, we are keeping track of visited nodes using ‘dist’ only, i.e if dist[j] is infinite then j-th node is unvisited. You can make a separate array ‘visited’ for this.
Create a queue, and insert a root node in it.
While queue is not empty
Pop the front element from the queue.
For any child found unvisited
dist [child] = dist [current_node] + 1
parent [child] = current_node
Insert child to queue
If a child is already visited (by other parent)
ans = min(ans, dist[child] + dist[current_node] + 1)
If ‘ans’ is still infinite, return -1, else return ‘ans’.

Solve now