Graph: Given a graph with source and destination, count all the possible path between two vertices

Problem Statement:

You are given a directed non cyclic graph, and 2 nodes having source and destination.

You need to return the count of two paths from source to destination.

Example:

Solution Explanation:

We will use DSF to solve the problem.

DSF should be used of the graph is non cyclic graph.

In DSF we recursively check all the possible paths by visiting all the unvisited neighbors.

We will use adjacency list to represent the connection between the nodes and visited array to keep track of all the nodes that are visited.

Time Complexity: O(2^n)
Space Complexity: O(n)

Code Solution
——————

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

void dfs(int node, int dest, vector<vector<int>> &graph,
         vector<bool> &visited, int &count) 
{
    
    if (node == dest) 
    {
        count++;
        return;
    }

    // mark current node as visited
    visited[node] = true;

    for (int neighbor : graph[node]) 
    {
        if (!visited[neighbor]) 
        {
            dfs(neighbor, dest, graph, visited, count);
        }
    }

    visited[node] = false;
}

int solution(int n, vector<vector<int>> &edgeList,
               int source, int destination) 
{
	
	// add into the edge list
    vector<vector<int>> graph(n + 1);

    for (auto &edge : edgeList) 
    {
        int u = edge[0];
        int v = edge[1];
        graph[u].push_back(v);
    }

    // create a visited array
    vector<bool> visited(n + 1, false);
    int count = 0;

    // start from source
    dfs(source, destination, graph, visited, count);

    return count;
}

int main() 
{
    
    int n = 5;

    vector<vector<int>> edgeList = 
    {
        {1, 2}, {1, 3}, {1, 5},
        {2, 5}, {2, 4}, {3, 5}, {4, 3}
    };

    int source = 1;
    int destination = 4;

    cout << solution(n, edgeList, source, destination);

    return 0;
}

Output

1