cf-645D. Robot Rapping Results Report(判断是否是惟一的拓扑序列)

题意】：
给出一个有向图，确定最小的k，通过前k条边就能确定唯一的拓扑序列。若整个图不存在唯一的拓扑序列，输出-1

#include<bits/stdc++.h>
using namespace
std;
#define ll long long
#define pb push_back
#define inf 2099999999
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep1(i,a,b) for(int i=a;i>=b;i--)
const int N=1e5+10;
vector<int>G[N];
int n,m,a1[N],a2[N];
int in[N];
/**
能决定出顺序就说明拓扑排序是一条直线
那么如果出现一个数后面有两个数就是错误的
二分答案
可以用队列判断每当pop一个数之后如果队列里面还有数
说明不可行
*/
bool check(int mid)
{
memset(in,0,sizeof(in));
for(int i=0;i<=n;i++)
G[i].clear();
for(int i=1;i<=mid;i++)
G[a1[i]].pb(a2[i]),in[a2[i]]++;
queue<int>q;
for(int i=1;i<=n;i++)
if(in[i]==0)
q.push(i);
while(!q.empty())
{
int t=q.front();
q.pop();
if(!q.empty())
return false;
for(int i=0;i<G[t].size();i++)
{
int v=G[t][i];
in[v]--;
if(in[v]==0)
q.push(v);
}
}
return true;
}
int main()
{
#ifdef LOCAL_DEFINE
freopen("D://rush.txt", "r", stdin);
#endif
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>a1[i]>>a2[i];
int l=1,r=m,ans=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
r=mid-1,ans=mid;
else
l=mid+1;
}
cout<<ans<<endl;
}