90求助

B3644 【模板】拓扑排序 / 家谱树

collegiate @ 2024-11-19 17:02:29

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
ll ind[N];
bool used[N];
vector<ll> G[N];
ll n,x,y,op,maxn;
queue<ll> q;

void topu(){
    ll cnt=0;
    while(!q.empty()){
        ll top=q.front();q.pop();
        cnt++;
        for(auto y:G[top]){
            if(used[y]){
                ind[y]--;
                if(ind[y]==0) q.push(y);                
            }
        }
    }
    if(cnt==n) cout<<"Yes";
    else cout<<n-cnt;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        maxn=max(maxn,x);
        used[x]=1;
        while(y--){
            cin>>op;
            maxn=max(maxn,op);
            G[x].push_back(op); 
            ind[op]++;
        }
    }
    for(int i=1;i<=maxn;i++){
        if(ind[i]==0 && used[i]) q.push(i);
    }
    topu();
    return 0;
}

|