Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define F first
- #define S second
- using namespace std;
- typedef long long ll;
- typedef pair<ll,ll> pll;
- const int MX=1e6+9;
- const int SQ=300;
- const ll mod=1e9+7;
- int n,deg[MX],x,y,m;
- ll dp[MX];
- vector<int>v[MX];
- int main(){
- while(scanf("%d",&n)){
- for(int i=0;i<n;i++)deg[i]=0,v[i].clear(),dp[i]=0;
- for(int i=0;i<n;i++){
- int k;scanf("%d",&k);
- while(k--){
- int x;scanf("%d",&x);
- v[i].push_back(x);
- deg[x]++;
- }
- }
- queue<int>q;
- for(int i=0;i<n;i++){
- if(deg[i]==0)q.push(i),dp[i]=1;
- }
- while(!q.empty()){
- int x=q.front();q.pop();
- for(auto pp:v[x]){
- dp[pp]+=dp[x];
- deg[pp]--;
- if(deg[pp]==0)q.push(pp);
- }
- }
- ll ans=0;
- for(int i=0;i<n;i++){
- if(v[i].size()==0)ans+=dp[i];
- }
- cout<<ans<<endl;
- }
- }
- /*
- 6
- 3 1 2 5
- 3 2 3 4
- 2 3 4
- 0
- 1 5
- 0
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement