Simple paths

Easy
0/40
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in companies
WalmartFlipkart limited

Problem statement

You are given a directed graph containing ‘N’ nodes and ‘M’ edges, where each edge is associated with some cost. Each node in the graph can have at most one incoming edge and at most one outgoing edge. A node is called a ‘source’ node if it has an outgoing edge but no incoming edge. And a node is called a ‘destination’ node if it has an incoming edge but no outgoing edge.

A simple path in this graph is a path that starts from a ‘source’ node and ends at a ‘destination’ node. The cost of such a path is the minimum cost among all edges traversed on this path.

Your task is to find all simple paths along with their costs for the given graph.

Note :-

Given graph may be not connected.
Nodes are numbered from [1, 2 ….. N] in input data.
Output data must be sorted by ‘source’ nodes.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains 'T', denoting the number of tests.
For each Test :
The first line contains two space-separated integers, 'N' and 'M', denoting the number of nodes and number of edges, respectively.
Next 'M' lines contain three integers 'x[i]', 'y[i]', 'w[i]' denoting there is a directed edge from node 'x[i]' to node 'y[i]', and having cost 'w[i]'.
Output Format: 
For each Test :
The first line contains an integer 'P', denoting the number of simple paths.
Next 'P' lines contain three integers 'a[i]', 'b[i]', 'c[i]' denoting there is a path starting from node 'a[i]', ending at node 'b[i]' and having cost 'c[i]'.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints - 
1 <= T <= 5
1 <= N, M <= 10^5
1 <= x[i], y[i] <= N  i ∈  (1, M)
0 <= w[i] <= 10^9  i ∈  (1, M)
Note - Sum of N and sum of M over all test cases does not exceed 10^5.

Time Limit: 1 sec
Sample Input 1 :
1
9 6
3 1 10
2 8 13
4 6 19
7 4 8
5 9 21
9 7 11
Sample Output 1 :
3
2 8 13
3 1 10
5 6 8
Explanation for Sample Input 1:
There are 3 simple paths in given graph, which are :-
Path (3 -> 1) with cost 10.
Path (2 -> 8) with cost 13.
Path (5 -> 9 -> 7 -> 4 -> 6) with cost 8, as minimum(21, 11, 8, 19) = 8.
Sample Input 2 :
2
4 2
1 2 19
3 4 12
3 3
1 2 12
2 3 9
3 1 8
Sample Output 2 :
2
1 2 19
3 4 12
0
Hint

Does each ‘source’ node necessarily have its distinct ‘destination’ node?

Approaches (1)
Depth First Search

Approach:  From given constraints on edges of the graph, it can be observed that each ‘source’ node will necessarily have a corresponding ‘destination’ node. Hence, the count of ‘source’ nodes is the number of simple paths.

A ‘source’ node can be easily identified by checking the presence of incoming and outgoing edges to/from it. From each ‘source’ node, run a DFS and keep track of the minimum weighted edge. The DFS will run until it finds a node for which no outgoing node is found; it’s our ‘destination’ node.


 

Algorithm:

  • Create three vectors as follows :
    • comingFrom: stores starting node of an edge, which ends at i-th node.
    • goingTo: stores the ending node of an edge, which starts from i-th node.
    • weight: stores the weight of an edge, which starts from i-th node.
  • Fill above three vectors using given edges.
  • Create a 2D vector ‘ans’ where each row denotes one path and has three values: ‘source’, ‘destination’, and ‘cost’.
  • Iterate a for loop from i = 1 to N.
    • If the i-th node is a ‘source’ node (i.e. comingFrom[i] is zero and goingTo[i] is non-zero)
      • Initialize the cost of this path with infinity.
      • Traverse consecutive outgoing edges until a node with no outgoing edge is found. For each edge with a smaller weight, update the cost of the path.
    • Append this path (source, destination, cost) to ‘ans’.
  • Return ‘ans’.
Time Complexity

O(N + M), where N and M are the number of nodes and edges, respectively.

DFS traversal on a graph of connected components has O(N+M) complexity. Hence overall time complexity becomes O(N + M).

Space Complexity

O(N), where N is the number of nodes.

We are creating three vectors of length N. Hence overall space complexity becomes O(N).

Code Solution
(100% EXP penalty)
Simple paths
Full screen
Console