Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. using namespace std;
  5. typedef long long ll;
  6. typedef pair<ll,ll> pll;
  7. const int MX=1e6+9;
  8. const int SQ=300;
  9. const ll mod=1e9+7;
  10. int n,deg[MX],x,y,m;
  11. ll dp[MX];
  12. vector<int>v[MX];
  13. int main(){
  14.     while(scanf("%d",&n)){
  15.         for(int i=0;i<n;i++)deg[i]=0,v[i].clear(),dp[i]=0;
  16.         for(int i=0;i<n;i++){
  17.             int k;scanf("%d",&k);
  18.             while(k--){
  19.                 int x;scanf("%d",&x);
  20.                 v[i].push_back(x);
  21.                 deg[x]++;
  22.             }
  23.         }
  24.         queue<int>q;
  25.         for(int i=0;i<n;i++){
  26.             if(deg[i]==0)q.push(i),dp[i]=1;
  27.         }
  28.         while(!q.empty()){
  29.             int x=q.front();q.pop();
  30.             for(auto pp:v[x]){
  31.                 dp[pp]+=dp[x];
  32.                 deg[pp]--;
  33.                 if(deg[pp]==0)q.push(pp);
  34.             }
  35.         }
  36.         ll ans=0;
  37.         for(int i=0;i<n;i++){
  38.             if(v[i].size()==0)ans+=dp[i];
  39.         }
  40.         cout<<ans<<endl;
  41.     }
  42. }
  43. /*
  44. 6
  45. 3 1 2 5
  46. 3 2 3 4
  47. 2 3 4
  48. 0
  49. 1 5
  50. 0
  51. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement