fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define lli long long int
  4. #define inf 1000000000
  5. #define pb push_back
  6. #define mp make_pair
  7. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  8. #define endl "\n"
  9. #define yoi cout<<"yo"<<endl;
  10. #define debug(x) cerr << #x << " is " << x << endl;
  11. #define all(x) x.begin(),x.end()
  12. const int mod=1e9+7;
  13. lli dp[100001][2];
  14. int indegree[100001];
  15. void dfs(vector<vector<int> >&v,int i){
  16.     int j;
  17.     for(j=0;j<v[i].size();j++){
  18.         dp[v[i][j]][0]=(dp[v[i][j]][0]+dp[i][1])%mod;
  19.         dp[v[i][j]][1]=(dp[v[i][j]][1]+dp[i][0])%mod;
  20.         indegree[v[i][j]]--;
  21.         if(!indegree[v[i][j]])
  22.         dfs(v,v[i][j]);
  23.     }
  24. }
  25. int main(){
  26. IOS;
  27. int t;
  28. cin>>t;
  29. while(t--){
  30.     lli n,m,u,x,y,i;
  31.     cin>>n>>m>>x;
  32.     memset(dp,0,sizeof(dp));
  33.     memset(indegree,0,sizeof(indegree));
  34.     vector<vector<int> > v(n+1);
  35.     for(i=0;i<m;i++){
  36.         cin>>u>>y;
  37.         v[u].pb(y);
  38.         indegree[y]++;
  39.     }
  40.     dp[x][0]=0;
  41.     dp[x][1]=1;
  42.     dfs(v,x);
  43.     for(i=1;i<=n;i++){
  44.         cout<<dp[i][0]<<" ";
  45.     }
  46.     cout<<endl;
  47. }
  48. }
  49.  
Success #stdin #stdout 0s 17192KB
comments (?)
stdin
copy 
2
5 4 1
1 2
2 3
1 4
3 5
5 5 1
1 2
2 3
1 4
3 5
1 5
stdout
copy 
0 1 0 1 1 
0 1 0 1 2
https://ideone.com/eEkHZA
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!