Advertisement
Josif_tepe

Untitled

Nov 20th, 2022
697
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. #include <cstring>
  6. #include <set>
  7. #include <map>
  8. using namespace std;
  9. int n, m;
  10. vector<int> graph[200005];
  11. int dp[200005];
  12. int rec(int node) {
  13.     if(node == n) {
  14.         return 1;
  15.     }
  16.     if(dp[node] != -1) {
  17.         return dp[node];
  18.     }
  19.     int result = 0, MOD = 1e9 + 7;
  20.     for(int i = 0; i < (int) graph[node].size(); i++) {
  21.         int neigh = graph[node][i];
  22.         result += rec(neigh);
  23.         result %= MOD;
  24.     }
  25.     return dp[node] = result;
  26. }
  27.  
  28. int main(int argc, const char* argv[]) {
  29.     cin >> n >> m;
  30.     for(int i = 0; i < m; i++) {
  31.         int a, b;
  32.         cin >> a >> b;
  33.         graph[a].push_back(b);
  34.     }
  35.     memset(dp, -1, sizeof dp);
  36.     cout << rec(1) << endl;
  37.     return 0;
  38. }
  39.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement