Count Ways

Easy
0/40
Average time to solve is 24m
36 upvotes
Asked in companies
FacebookGoldman SachsAmazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
4 3 2
1 2
2 3
3 4
Sample Output 1:
3
Explanation for Sample Input 1:
From node 2 we can reach each of 2, 3, 4 nodes only in one way.
Sample Input 2:
5 6 2
1 2
2 3
3 4
4 5
3 5
1 5
Sample Output 2:
5
Hint

Iterate over all possible paths.

Approaches (2)
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):

  1. Initialize 'COUNT with 1.
  2. 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).
  3. Return ‘COUNT’.
Time Complexity

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). 

Space Complexity

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.

Code Solution
(100% EXP penalty)
Count Ways
Full screen
Console