CodeForces - 645D Robot Rapping Results Report

题面在这里！

 

    要有唯一的拓扑序的话，拓扑排序的时候队列就必须一直只有一个元素，二分check一下就好啦。

 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int hd[N],to[N],ne[N],num,n,m;
int d[N],ans=-1,mid;
inline void add(int x,int y){ to[++num]=y,ne[num]=hd[x],hd[x]=num;}
inline bool check(){
memset(d,0,sizeof(d)); int x=0,y;
for(int i=1;i<=mid;i++) d[to[i]]++;
for(int i=1;i<=n;i++) if(!d[i]) if(!x) x=i; else return 0;
for(;x;){
y=x,x=0;
for(int i=hd[y];i;i=ne[i]) if(i<=mid&&!(--d[to[i]]))
if(!x) x=to[i]; else return 0;
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,uu,vv;i<=m;i++)
scanf("%d%d",&uu,&vv),add(uu,vv);
int l=1,r=m;
while(l<=r){
mid=l+r>>1;
if(check()) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%dn",ans);
return 0;
}