平平无奇的拓扑排序,发现存的出度(out数组)好像没用到。求调!
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
int n,m,u,v,ind[100005],out[100005],ans;
queue<int> q;
vector<int> p[100005];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>u;
cin>>m;
for(int j=1;j<=m;j++){
cin>>v;
ind[v]++;
out[u]++;
p[u].push_back(v);
}
}
for(int i=1;i<=n;i++){
if(ind[i]==0){
q.push(i);
}
}
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=0;i<p[now].size();i++){
int pos=p[now][i];
ind[pos]--;
}
}
for(int i=1;i<=n;i++){
if(ind[i]<=0) ans++;
}
if(ans==n) cout<<"YES";
else cout<<n-ans;
}