Advertisement
Josif_tepe

Untitled

Jun 9th, 2022
1,007
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. int n;
  7. int m;
  8.  
  9. int dp[100005];
  10. vector<int>graph[100005];
  11. int rec(int node){
  12.     int result=0;
  13.     if(node==n){
  14.        return 1;
  15.     }
  16.     if(dp[node]!=-1){
  17.         return dp[node];
  18.     }
  19.     int MOD = 1e9 + 7;
  20.     for(int i=0; i<graph[node].size(); i++){
  21.         int sosed=graph[node][i];
  22.         result+=rec(sosed);
  23.         result %= MOD;
  24.     }
  25.     return dp[node]=result;
  26. }
  27. int main()
  28. {
  29.  
  30.  
  31.  
  32.     cin>>n>>m;
  33.     for(int i=0; i<m; i++){
  34.     int a, b;
  35.     cin>>a>>b;
  36.     graph[a].push_back(b);
  37.     }
  38.     memset(dp, -1, sizeof dp);
  39.  
  40.     cout<<rec(1);
  41.     return 0;
  42. }
  43.  
Advertisement
RAW Paste Data Copied
Advertisement