Graph: Get all the paths from source to destination

Problem Statement:

You are given a directed acyclic graph and n nodes from 0 to n-1.

You need to find the number of paths from 0th node to n-1 node.

Example

Input: graph = [[1,2],[3],[3],[]]

Visual Representation of the graph 
0 -> 1
|    |
v    v
2 -> 3

Output: [[0,1,3],[0,2,3]]

Solution Explanation:

We can solve the problem with the help of DFS approach.

We start with the source node and recursively call the DFS function to keep adding the current node in to the result vector.

If we reach the node n-1, then add the path to the result.

If not, keep recursively calling the function to arrive at the solution.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


vector<vector<int>> result;    //Result vector

void solve(vector<vector<int>> &graph, vector<int> &path, int i)
{
    path.push_back(i); // add node into the curent path

    if(i==graph.size()-1) 
    	result.push_back(path); // if we reach dest node, then add into the result
    
    for(auto adj : graph[i]) 
    		solve(graph, path, adj); // call the dfs recursively
    
    path.pop_back();  //Backtracking
}

vector<vector<int>> solution(vector<vector<int>>& graph) 
{
    vector<int> currPath;

    solve(graph, currPath, 0); 
    
    return result;
}


int main() 
{
    
    int n = 5;

    vector<vector<int>> graph = 
    {
        {1, 2}, {3}, {3}, {}
    };

 	vector<vector<int>> paths = solution(graph);

    for (const auto &path : paths) 
    {
        for (int vtx : path) 
        {
            cout << vtx << " ";
        }
        cout << endl;
    }
    return 0;
}

Output

0 1 3 
0 2 3