Advertisement
savrasov

123123

Jun 13th, 2017
404
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <iomanip>
  4. #include <cmath>
  5. #include <set>
  6. #include <vector>
  7. #include <fstream>
  8. #define pb push_back
  9.  
  10. using namespace std;
  11.  
  12. typedef long long ll;
  13. typedef long double ld;
  14. const int mod = 1e9 + 7;
  15.  
  16. int pr[300000], d[300000], h, t, q[1000000];
  17. bool used[300000];
  18. vector<set<int> > g(200001);
  19.  
  20. int main()
  21. {
  22.     //freopen("input.txt", "r", stdin);
  23.     //freopen("output.txt", "w", stdout);
  24.     int n, m, a, b, v;
  25.     cin >> n>> m;
  26.     for(int i = 0; i < m; i++)
  27.     {
  28.         cin >> a >> b;
  29.         a--;
  30.         b--;
  31.         g[a].insert(b);
  32.         if(g[b].find(a) != g[b].end()) d[a] = d[b] = -1;
  33.     }
  34.     d[0] = 1;
  35.     q[h++] = 0;
  36.     for(;h != t;)
  37.     {
  38.         v = q[t];
  39.         t = (t + 1) % 1000000;
  40.         for(set<int>::iterator i = g[v].begin(); i != g[v].end(); i++)
  41.         {
  42.             if(d[*i] != -1 && (!pr[*i] || pr[*i] == v))
  43.             {
  44.                 d[*i] = (d[*i] + d[v]) % mod;
  45.                 q[h] = *i;
  46.                 h = (h + 1) % 1000000;
  47.                 pr[*i] = v;
  48.             }
  49.             else d[*i] = -1;
  50.         }
  51.     }
  52.     for(int i = 0; i < n; i++)
  53.         if(i) cout << d[i] << endl;
  54.     return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement