Last Updated: 5 Apr, 2021
NINJA’S TRIP
Moderate
Asked in company
Ninja is in a very tense situation as he goes on a trip of mountains but in between his trip, he comes to know that there are various paths between mountains and each mountain has its own limit of weight. Now he starts looking at the map of the city to look for the desired places. This map is in the form of undirected weighted graphs where the edge weight represents the weight mountains can hold between two paths.
Now ninja has some places in mind where he wants to go but with the limit on weight. So help our ninja in checking whether he can go to that place or not.
Your task is to give the answer to ninja queries where he gives you ‘2’ points representing his current location and ending location. You have to return ‘True’ if it is possible to go from that location within the required limit and return ‘False’if it is not possible to go.
Example:
Suppose our query array is [ [ 0, 1, 2 ], [ 0, 2, 5 ] ] so we return False for the first query as there is no edge with a distance less than ‘2’ from ‘0’ to ‘1’.
For the second query, we return ‘True’ as we can indirectly i.e from ‘0’ to ‘1’ which has the weight ‘2’ less than ‘5’ and then ‘1’ to ‘2’ which has the weight ‘4’ less than ‘5’.
Input Format:
The first line of input contains a ‘T’ number of test cases.
The first line of each test case contains a number ‘N’ and ‘M’ representing the number of vertices and rows in array ‘EDGELIST’ respectively. Then, ‘M’ lines follow.
Each line contains ‘3’ space-separated integers denoting the row values where the first value is the starting point, the second value is the ending point and the third value is the weight of the edge.
After ‘M’ lines contain an integer value ‘Q’ denoting the number of queries then ‘Q lines follow
Each line contains ‘3’ space-separated integers denoting the row values where the first value is the starting point, the second value is the ending point and the third value is the weight of the edge.
Output Format:
For each test case, print a single line containing the answer for each query, denoted by ‘True’ if it is possible to go else return ‘False’.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
2 <= N <= 1000
2 <= | EDGELIST | , | QUERY | <= 1000
0 <= EDGELIST[i][j], QUERY[i][j] <= N - 1
Where ‘T’ represents the number of test cases, ‘N’ represents the number of vertices and query length represents the size of the ‘QUERY’ array and ‘EDGELIST’ length represents the size of the ‘EDGELIST’ array.
Time Limit: 1 seC.
Approaches
The idea here is to use dfs and for each query, we have to check that from a given node in query is it possible to reach a given other node in the query by using limit on the weight of edges.
- We create a 2-d array for taking in consideration whether we have visited that node from a particular node or not.
- Now we start our dfs for each and every query and try to reach the target by calling recursively for the next node and in every recursive call we check if the weight of the edge is greater than the limit we return False.
- If we reached the target we return True and repeat the above steps for each query.
In this approach, we are using a union data structure for making the combination so now there is no need of checking edges, again and again, we just take the union of all edges which satisfies the limit.
- First, we sort the queries on the basis of given limits from smallest to largest so that we are able to compute our graph from the bottom up, and also we store the original index of the query array as we have to return bool value for each query by maintaining the order.
- Now we sort our edge list in the same fashion smallest to largest.
- Now we create starting disjoint set by passing value from the edge list and store the connected components in it along with the rank of each element.
- Now after that, we can easily use the find function for each query which gives us if whether is connected in any way and if weight is greater than the limit or not.
- If we are able to go to that location we store the ‘True’ in our ‘ans’ array.
- If we are not able to go we store false for that particular query.
- Repeat the same steps for each query and in the last return ‘ans’ array.
Similar problems