New update is available. Click here to update.
sidenav-btnClose
Topic list
Find All Paths In DAG
MEDIUM
30 mins
3 upvotes
Graph
Topics (Covered in this problem)
Problem solved
Skill meter
Graph
-
Other topics
Problem solved
Skill meter
Strings
-
Matrices (2D Arrays)
-
Sorting
-
Binary Search
-
Linked List
-
Stacks & Queues
-
Trees
-
Dynamic Programming
-
Greedy
-
Tries
-
Arrays
-
Binary Search Trees
-
Heap
-
Bit Manipulation
-

Find All Paths In DAG

Contributed by
Shivam Mehla
Medium
Avg time to solve 30 mins
Success Rate 70 %
Share
3 upvotes

Problem Statement

Given a connected directed acyclic graph having ‘N’ nodes and ‘M’ edges. A matrix ‘edges’ of size M x 2 is given, which represents the ‘M’ edges such that there is an edge directed from node edges[i][0] to node edges[i][1].

You are supposed to find all possible paths from node 0 to node n - 1.

Note
Nodes are numbered from 0 to N - 1.

The graph given is connected.

Print the path[][] in sorted order i.e path[i] is an array containing the path from 0 to n-1, and path[i] is lexicographically smaller than path[i + 1] then path[i] should appear before path[i + 1].

Assume we have two solutions
S1: A1 B1 C1 D1  
S2: A2 B2 C2 D2

S1 is lexicographically smaller than S2 iff,
A1 < A2 OR
A1 = A2 AND B1 < B2 OR
A1 = A2 AND B1 = B2 AND C1 < C2 OR 
A1 = A2 AND B1 = B2 AND C1 = C2 AND D1 < D2
For Example :
The following is an example of DAG i.e a directed graph with no cycles in it. 

alt
text

Detailed explanation ( Input/output format, Notes, Constraints, Images )
Sample Input 1 :
2
6 5
0 1
0 2
2 5
3 4
4 2
5 6
0 1
2 1
1 4
2 4
0 4
3 1
Sample Output 1 :
0 2 5
0 1 4
0 4
Explanation For Sample Output 1:
For the first test case, 
All possible paths from 0 to 5 are:
0 -> 2 -> 5

For the second test case,
All possible paths from 0 to 5 are:
0 -> 1 -> 4
0 -> 4
As the first path appears before so it is printed first and then the second path.

Sample Input 2:

2
4 4
0 1
0 2
0 3
1 2
2 1
0 1
Sample Output 2:
0 3
0 1
Reset Code
Full screen
copy-code
Console