Possible paths between 2 vertices

Problem Statement - link #

Given a Directed Graph having V nodes numbered from 1 to V, and E directed edges. Given two nodes, source and destination, count the number of ways or paths between these two vertices in the directed graph. These paths should not contain any cycle. Note: Graph doesn’t contain multiple edges, self-loop, and cycles.

Your Task: You don’t need to read, input, or print anything. Your task is to complete the function countPaths(), which takes the integer V denoting the number of vertices, adjacency list adj, integer source, and destination as input parameters and returns the number of paths in the graph from the source vertex to the destination vertex.

Expected Time Complexity: O(V!)
Expected Auxiliary Space: O(V)

Examples #

Example 1:

Input:
V = 5, E = 7
Edges of Graph = 
{0, 1}
{0, 2}
{0, 4}
{1, 3}
{1, 4}
{2, 4}
{3, 2}
source = 0 
destination = 4

Output: 4
Explanation: 

There are 4 paths from 0 to 4.
0 -> 4
0 -> 1 -> 4
0 -> 2 -> 4
0 -> 1 -> 3 -> 2 -> 4

Constraints #

• 1 ≤ V, E ≤ 100
• 1 ≤ source, destination ≤ V

Solutions #

class Solution
{
    public:
    // Function to count paths between two vertices in a directed graph.
    int countPaths(int V, vector<int> adj[], int source, int destination) {
        // Code here
        if(source==destination) return 1;
        int count = 0;
        for(int v: adj[source])
            count += countPaths(V,adj,v,destination);
        return count;
    }
};