Close
Topic list
Find All Paths In DAG
MEDIUM
30 mins
Graph
Topics (Covered in this problem)
Problem solved
Skill meter
Graph
-
Other topics
Problem solved
Skill meter
Strings
-
Matrices (2D Arrays)
-
Sorting
-
Binary Search
-
-
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

## Problem Statement

#### 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.
``````

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
``````
Console