Thomas and Friends

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
1 upvote
Asked in company
Uber

Problem statement

Thomas is a Tank engine on the island of Sodor. There are total ‘N’ cities on this island connected with ‘m’ tracks. All the cities on this island are connected to each other, directly or indirectly. Thomas and all his engine friends travel from city ‘a’ to city ‘b’ daily but might use different routes. Some of these tracks are present on all the paths from the city ‘a’ to ‘b’. Due to excessive load on these tracks, all of these tracks are not in good condition, so one day Thomas asks The Fat Controller to repair all the tracks that are present on all the paths from ‘a’ to ‘b’. Help the Fat controller to count all these tracks.

For Example: 
n = 5, m = 5, a = 1, b = 0


Now in this example, all the paths from ‘1’ to ‘0’ are:
1 -> 4 -> 0
1 -> 5 -> 4 -> 0
The track 4 -> 0 is present in both of these paths. Hence the answer is 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. Then each test case follows:

The first line of each test case contains two integers, ‘N’ and ‘M’, denoting the number of cities and tracks, respectively.

The next ‘M’ lines of the test case contain two space-separated integers, ‘x’ and ‘y’, denoting a track between ‘x’ and ‘y’.

The last line of the test case contains two space-separated integers, ‘a’ and ‘b’, denoting the starting and ending city of Thomas and his friends.
Output Format : 
For each test case, print the total number of common tracks between all the paths from ‘a’ to ‘b’.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints : 
1 <= T <= 10
1 <= N <= 1000
N-1 <= M <= (V * (V - 1)) / 2
0 <= a, b <= V - 1

Time Limit: 1sec
Sample Input 1 :
2
4 4
0 1
0 3
1 2
2 3
1 3
6 6
1 2
2 3
2 4
4 5
3 5
5 0
1 0
Sample Output 1 :
0
2
Explanation For Sample Output 1 :

In the first test case, there are two paths from 1 to 3. I.e. 1 -> 2 -> 3 or 1 -> 0 -> 3 and both these paths have no common track.
Hence the answer is 0.


In the second test case, there are two different paths from 1 to 0. i.e. , 1 -> 2 -> 3 -> 6 -> 0 and 1 -> 2 -> 4 -> 6 -> 0. Having two common tracks, 1 -> 2 and 6 -> 0.
Hence the answer is 2.
Sample Input 2 :
2
2 1
0 1
1 0
5 4
0 1
1 2
2 3
3 4
0 4
Sample Output 2 :
1
4
Hint

Iterate through the graph using DFS and count all the common paths using the concept of bridges.

Approaches (1)
Depth-first Search

In this approach, iterate through the whole graph using DFS and take three vectors inTime, low, outTime, in which we will store the first time we will visit that node, the minimum time we encountered the node and the time when we finally left the current node, respectively.

 

The steps are as follows :

  • In the “main” function:
    • Take an integer “ans” in which we will store the count of the tracks.
    • Call the “dfs” function and pass the vectors, “inTIme”, “outTime”, “low”, city a and b.
    • Return “ans”.
  • In the “dfs” function:
    • Mark the current node as visited.
    • Update the InTime and low of current node = “timer”.
    • Iterate through all the nodes connected to the current node,
      • If the current node equals the parent node, skip the current node.
      • If the current node is not visited:
        • Call the “dfs” function for the current node.
        • Check if the “low[i]” > “in[node]”:
          • If the “inTime[i]” <= “inTime[b]” and outTime[i] >= “outTime[b]”:
            • Increment “ans”.
        • Update the “low[node]” = min(“low[node]”, “low[adj]”).
      • Else Update the “low[node]” = min(“low[node]”, “in[i]”).
    • Update the value of “outTime[node]” = “timer++”;
Time Complexity

O(V + E). Where V is the number of cities and E is the number of Tracks.

 

Since we are implementing Depth-first search, which is a linear task,

Hence the time complexity is O(V + E).

Space Complexity

O(V), Where V is the number of cities.

 

We are using arrays of size V.

Hence the space complexity is O(V).

Code Solution
(100% EXP penalty)
Thomas and Friends
Full screen
Console