Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 22 Feb, 2021

Moderate

Print -1 if a node is not reachable from the given source node.

```
Consider the following DAG consists of 5 nodes and 7 edges, Let the source node ‘Src’ be 0.
```

```
Then the maximum distance of node 0 from the source node 0 is 0. (the distance of a node from itself is always 0).
The maximum distance of node 1 from the source node 0 is 3. The path that gives this maximum distance is 0 -> 1.
The maximum distance of node 2 from the source node 0 is 10. The path that gives this maximum distance is 0 -> 2.
The maximum distance of node 3 from the source node 0 is 15. The path that gives this maximum distance is 0 -> 2 -> 3.
The maximum distance of node 4 from the source node 0 is 54. The path that gives this maximum distance is 0 -> 1 -> 4.
Thus we should print 0 3 10 15 54
```

```
The first line of input contains an integer ‘T’ denoting the number of test cases. then ‘T’ test cases follow.
The first line of each test case consists of three space-separated integers ‘N’, ‘E’, and ‘Src’ representing the number of nodes, number of edges, and the given source node in the given DAG respectively.
The next ‘E’ lines consist of three space-separated integers ‘U’, ‘V’, ‘W’ representing that there is a directed edge from node U to V having weight ‘W’.
```

```
For each test case, print ‘N’ space-separated integers where ’ith’ integer gives the maximum distance of node ‘i’ from the source node ‘Src’.
The output of each test case will be printed in a new line.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 50
1 <= N <= 10^4
0 <= E <= 10^4
0 <= Src <= N-1
0 <= U, V <= N-1
1 <= W <= 10^5
Where ‘T’ is the total number of test cases, ‘N’, ‘E’, and ‘Src’ representing the number of nodes, number of edges, and the given source node in the given DAG respectively. ‘U’, ‘V’, ‘W’ represents that there is a directed edge from node U to V having weight ‘W’.
Time limit: 1 sec
```

First we create an integer array ‘**maxDistances**’ of size ‘**N**’ and fill it with -1,** maxDistances[i] **will give the maximum distance of node ‘**i’** from the given source node. We will then recursively try out all paths starting from the source node. We will also use an integer variable ‘**dist**’ to track distance covered so far on this path. Whenever we reaches any node ‘i’ we update its maximum distance i.e **maxDistances[i] **with maximum of its current value and ‘**dist**’.

- Create an adjacency list ‘
**adj**’, such that**adj[i][j]**is a list of two integers**[v, w],**representing that that ‘**jth**’ adjacent node of ‘**i’**is node ‘**v**’ and the weight of directed edge**i -> v**is**‘w**’. - Create a list of integers
**'maxDistances**' of size '**N'**and fill it with -1. - Create a boolean list ‘
**visited’**of size ‘**N**’ and fill it with false. - Make a recursive function
**findMaxDistancesHelper(current, dist),**where**‘current’**is the current node and**‘dist’**is the distance covered so far on this path (from source node ‘**Src**’ to**current**). In each recursive call do the following.- Update
**maxDistances[current] := maximum(maxDistances[current], dist).** **Mark current node visited i.e visited[current] := true.****Iterate over all of its adjacent nodes, 'node’ for which visited[node] is false, and for each of them call findMaxDistancesHelper(node, dist + weight of directed edge from current to this node).****Mark current node unvisited i.e visited[current] := false. This makes this node available to visit by other paths.**

- Update
- Return
**maxDistances**after calling this recursive function as**findMaxDistancesHelper(Src, 0).**In**maxDistances**now**maxDistances[i]**gives the maximum distance of node ‘**i’**from the given source node.

Topological Sorting of DAG is a linear ordering of vertices such that for every directed edge from vertex ‘u’ to vertex ‘v’, vertex ‘u’ comes before ‘v’ in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. We can find topological sorting of any DAG using this algorithm**.**

We can solve this problem of finding the longest paths in a directed graph in linear time if we process nodes in topological order, and update distances of their adjacent.

Note that if the graph is not DAG, then this problem is an NP-hard problem.

- Create an adjacency list ‘
**adj**’, such that**adj[i][j]**is a list of two integers**[v, w],**representing that that ‘**jth**’ adjacent node of ‘**i’**is node ‘**v**’ and the weight of directed edge**i -> v**is**‘w**’. - Create a list of integers
**'maxDistances**' of size '**N'**and fill it with -1. - Create a list ‘
**order’**of size ‘N’ that will have topological sorting of graph, Topological sorting can be found using this algorithm. - Assign
**‘maxDistances[Src]’ := 0.** - Run a loop where ‘i’ ranges from to ‘N’-1, and for each ‘i’ do following -:
- Initialize an integer variable
**current := order[i].** **If ‘maxDistances[current] == -1, then continue because this node is not reachable from the source node.**- Visit over all the adjacent nodes '
**neighbor**’ of node**current**, and update their distances**maxDistances[neighbor] := max(****maxDistances[neighbors], maxDistances[current] + weight of directed edge between node at current and neighbor)**

- Initialize an integer variable
**Return ‘maxDistances’.**

Similar problems

Minimum Swaps To Make Identical Array

Moderate

Posted: 22 Jan, 2022

Find Center of Star Graph

Easy

Posted: 26 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

COUNT ISLANDS

Moderate

Posted: 14 Sep, 2022

Distance to a Cycle in Undirected Graph

Moderate

Posted: 7 Nov, 2022