Last Updated: 23 Sep, 2020
Count Ways
Easy
Asked in companies
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.
Approaches
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,
- 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’.
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’.