Minimum walk

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].

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]’.

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

For case 1: N = 5, M = 6 There are 3 closed paths (same source and destination) which don't pass any road more than once. Paths are as follows :- 0 -> 1 -> 3 -> 2 -> 0 has a distance of 4 units. 2 -> 3 -> 4 -> 2 has a distance of 3 units. 0 -> 1 -> 3 -> 4 -> 2 -> 0 has a distance of 4 units. You can choose any city as a source in these paths, but distance remains the same. Among all these distances, 3 is the minimum possible. For Case 2: No path has the same source and destination, hence answer is -1.

Breadth First Search

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’.

Time Complexity

O(N * (N + M)), where N is the number of nodes/cities and M is the number of edges/roads.

BFS traversal from a single source takes time complexity of O(N + M). We are taking each vertex as a source node, so ‘N’ times BFS is called. Overall time complexity becomes O(N * (N+M)).

Space Complexity

O(N + M), where N is the number of nodes/cities and M is the number of edges/roads.

To store given connections / edges into graph representation, we need N+M space.

Next, we are creating two arrays ‘dist’ and ‘parent’ of length ‘N’. These two can be used again for each BFS.

Overall space complexity becomes O(N+M).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation for Sample Input 1:

Sample Input 2:

Sample Output 2: