Problem title
Difficulty
Avg time to solve

Count Distinct Element in Every K Size Window
Easy
15 mins
Fire in the cells.
Hard
15 mins
Merge Two BSTs
Moderate
10 mins
Search For Integers With Given Difference And At Given Distance
Moderate
20 mins
Construct Binary Tree From Inorder and Preorder Traversal
Easy
10 mins
Recycling Pens
Easy
15 mins
Max Path Value
Moderate
15 mins
Maximal AND Subsequences
Moderate
15 mins
Common Elements Present In All Rows Of Matrix
Moderate
25 mins
Area of a Rectangle
Easy
--
19

Count Ways

Difficulty: EASY
Contributed By
Ashwani |Level 1
Avg. time to solve
24 min
Success Rate
81%

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.
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
Reset Code
Full screen
copy-code
Console