Longest Path

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in companies
PhonePeAmazonZepto

Problem statement

You are given a Directed Acyclic Graph (DAG) with ‘E’ edges and ‘V’ vertices. A DAG is a type of graph with no directed cycles.

You have been given a source vertex ‘S’. Your task is to find the distance between ‘S’ and the farthest vertex reachable from ‘S’?

Example: Given a DAG graph :

Source node: 1
The farthest vertex in the above graph from vertex 1 is 2 via the route of vertex 3. So, the distance is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, the number of test cases.

The first line of each test case contains two single space-separated integers ‘V’ and ‘E’ representing the number of vertices and edges of the graph respectively.

The next ‘E’ lines will denote the edges of the graph where every edge is defined by two single space-separated integers ‘X' and 'Y', which signifies an edge from vertex 'X’ to vertex 'Y'.

The last line of each test case contains the single integer ‘S’, representing the Source vertex.
Output Format : 
For each test case, print the distance between ‘S’ and the farthest vertex reachable from ‘S’.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= V <= 10^3
1 <= E <= 3*10^3
1 <= X, Y <= V - 1
0 <= S <= V - 1

Time Limit : 1 sec
Sample Input 1 :
2
4 3
0 1
1 2
2 3
1
1 0
0
Sample Output 1 :
2
0
Explanation For Sample Input 1 :
For first test case, the graph will be :


The farthest vertex in the above graph from vertex 1 is 3 whose distance from vertex 1 is 2.

For second test case, the graph will be :


There are no vertices present other than 0, therefore distance will be 0.
Sample Input 2 :
1
4 3
0 1
1 3
3 2
1
Sample Output 2 :
2
Explanation For Sample Input 2 :
For the test case, the graph will be :


The farthest vertex in the above graph from vertex 1 is 2 whose distance from vertex 1 is 2.
Hint

Try to find the maximum number of vertices reachable from source by traversing.

Approaches (2)
Depth First Search

The basic idea is to find the maximum number of vertices that are reachable from the ‘SOURCE’ vertex. We can find that using simple DFS traversal. We don’t need to use any ‘VISITED’ array as the graph given is DAG which means it contains no cycle.

 

Here is the algorithm :
 

  1. Create a graph (say, ‘GRAPH’) using the ‘EDGES’ array in the form of adjacency list      (An array of lists in which ‘arr[i]’ represents the lists of vertices adjacent to the ‘ith’ vertex).
  2. Push the vertices in the ‘GRAPH’.
  3. Create a variable (say, ‘RES’) which will store the maximum reachable distance from the ‘SOURCE’.
  4. Call the ‘DFS’ function, DFS( ‘SOURCE’, ‘GRAPH’) which will calculate the maximum distance reachable from the source and store it in ‘RES’.
  5. Finally, return ‘RES’

 

DFS( ‘SOURCE’, ‘GRAPH’)
 

  1. Create a variable (say, ‘DIST’) that will store the maximum distance from the ‘SOURCE’ and initialize it to 0.
  2. Iterate all the adjacent vertices of the source vertex (say, iterator = ‘i’)
    • Call the ‘DFS’ function on the adjacent vertices of the ‘SOURCE’ vertex, which will calculate the maximum distance of the adjacent vertex from other vertices. Store it in a variable (say, ‘TEMP’)
    • Increment ‘TEMP’ by 1 (Distance between ‘SOURCE’ vertex and adjacent vertex is 1)
    • Calculate the maximum distance as the maximum of ‘DIST’ and ‘TEMP’.
  3. Finally, return ‘DIST’.
Time Complexity

O(|V| * (|V| + |E|)), where ‘V’ is the number of vertices and ‘E’ is the number of edges in the graph.

 

Total number of recursive calls for a vertex ‘V’ can be maximum upto (|V| + |E|) in which we will traverse every vertex and edge of the graph. Total number of vertices are ‘V’, therefore,  the overall time complexity will be O(|V| * (|V| + |E|)).

Space Complexity

O(|V| ^ 2), where ‘V’ is the number of vertices and ‘E’ is the number of edges in the graph.

 

For each vertex O(|V|), we store its adjacent neighbors O(|E|) it takes space O(|V| + |E|). But, in the worst case of a complete graph (each pair of vertices is connected by an edge), the space complexity will be O(|V| ^ 2).

Code Solution
(100% EXP penalty)
Longest Path
Full screen
Console