Count Ways
You have been given a directed graph of 'V' vertices and 'E' edges.

Your task is to count the total number of ways to reach different nodes in the graph from the given source node ‘S’. A way is called as different from others if the destination node or used edges differ.

As the total number of such ways can be large, print the total ways modulo 10 ^ 9 + 7.

Note:

1. Include the source node as a destination also. 2. There are no cycles in the given graph.

Input Format:

The first line of input will contain three integers 'V', 'E', and ‘S’, separated by a single space. From the second line onwards, the next 'E' lines will denote the directed edge of the graphs. Every edge is defined by two single space-separated integers 'A' and 'B', which signifies a directed edge from vertex 'A' to vertex 'B'.

Output Format:

For each input, print a single line containing a single integer denoting the total number of ways modulo 10 ^ 9 + 7.

Constraints:

1

Question

Count Ways

You have been given a directed graph of 'V' vertices and 'E' edges.

Your task is to count the total number of ways to reach different nodes in the graph from the given source node ‘S’. A way is called as different from others if the destination node or used edges differ.

As the total number of such ways can be large, print the total ways modulo 10 ^ 9 + 7.

Note:

1. Include the source node as a destination also.
2. There are no cycles in the given graph.

Input Format:

The first line of input will contain three integers 'V', 'E', and ‘S’, separated by a single space.

From the second line onwards, the next 'E' lines will denote the directed edge of the graphs.

Every edge is defined by two single space-separated integers 'A' and 'B', which signifies a directed edge from vertex 'A' to vertex 'B'.

Output Format:

For each input, print a single line containing a single integer denoting the total number of ways modulo 10 ^ 9 + 7.

Constraints:

1 <= 'S', 'V' <= 10 ^ 5
0 <= 'E' <= 2 * 10 ^ 5

Where ‘S’ represents the value of a given source node, ‘V’ represents the number of vertices and ‘E’ represents the number of edges.

Time Limit: 1 sec.

Accepted Answer

Brute Force

In the brute force approach, we will visit all paths from the source node to each node and increment the ‘COUNT’ for each path. We will use a recursive function that will be having a parameter as a source node. Now we will initialize our ‘COUNT’ for the current source node with 1 and call recursion on all the adjacent nodes to find the sub-paths and increase the ‘COUNT’. After iterating on all adjacent nodes, we will return the final ‘COUNT’. Here is an algorithm for a better explanation.

Algorithm:

countWays(SRCNODE, GRAPH):

Initialize 'COUNT with 1.
For all adjacent nodes directed from the source node,
1. Calculate ways by considering the adjacent node as the source node by having a recursive call and increment the count, i.e. ‘COUNT’ += countWays(ADJACENTNODE, GRAPH).
Return ‘COUNT’.

Space Complexity: OtherExplanation:

O(V + E), where ‘V’ denotes the total number of vertices, and ‘E’ denotes the total number of edges.

In the worst case, extra space is used by the recursion call stack.

Time Complexity: OtherExplanation:

O((V + E) ^ 2), where ‘V' denotes the total number of vertices, and 'E' denotes the total number of edges.

As, in the worst case, we have to check traverse every vertice for each vertice. Therefore, overall time complexity will be O((V + E) ^ 2).

Accepted Answer

Memoization Approach

In the approach, there exist repeated subproblems. To avoid calculating them every time, we will use the memoization concept to memorize the results once calculated. So that whenever we need again we can directly use the variable ‘RESULTS’ instead of calculating them again. Here is an algorithm for a better explanation.

Algorithm:

int countWays(SRCNODE, GRAPH, DP)

Initialize variable ‘COUNT’ with 1.
If we had already calculated the ‘RESULTS’, return DP[SRCNODE].
For all adjacent nodes directed from the source node,
Calculate ways by considering the adjacent node as the source node by having a recursive call and increment the count i.e ‘COUNT’ += countWays(ADJACENTNODE, GRAPH).
Store the results in memory, DP[SRCNODE] = ‘COUNT’.
Return ‘COUNT’.

Space Complexity: OtherExplanation:

O(V), where ‘V’ is the number of nodes/vertices in the graph.

In the worst case, we will be storing the count for each node.

Time Complexity: OtherExplanation:

O(V + E), where ‘V’ is the number of nodes and ‘E’ is the number of edges in the graph.

In the worst case, we will be visiting each node and edge once.