rt,思路是在拓扑排序时把当前所有入度为零的点找出来,统计其他点被他们指向的次数,如果只有一个点进队且这个点被指向的次数恰好是当前所有入度为零的点的个数,那么这个点的排名是可确定的
说的不清楚,看代码
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
addedge(u,v);
in[v]++;
}
queue<int>q;
for(int i=1;i<=n;i++){
if(!in[i])q.push(i);
}
if(q.size()==1)ab[q.front()]=1;
while(!q.empty()){
memset(pto,0,sizeof(pto));
int cnt=q.size();
queue<int>tmp;
while(!q.empty()){
int i=q.front();
q.pop();
for(int j=head[i];j;j=e[j].next){
int v=e[j].v;
pto[v]++;
in[v]--;
if(!in[v])tmp.push(v);
}
}
if(tmp.size()==1&&pto[tmp.front()]==cnt)ab[tmp.front()]=1;
while(!tmp.empty()){
q.push(tmp.front());
tmp.pop();
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(ab[i]){
ans++;
}
}
cout<<ans<<"\n";
return 0;
}