链接：https://ac.nowcoder.com/acm/contest/330/F
来源：牛客网
Applese 有一个QQ群。在这个群中，大家互相请教问题。如 b 向 a 请教过问题，就把 a 叫做是 b 的"老板"。这样一个群中就会有很多老板。
同时规定：如果 a 是 b 的老板，b 是 c 的老板，那么 a 也是 c 的老板。
为了不破坏群里面和谐交流的氛围，Applese 定了一个群规：不允许出现 a 既是 b 的老板， b 又是 a 的老板。
你需要帮助 Applese 判断大家是否遵守了群规。
第一行两个整数 n, m，表示群里的人数以及请教问题的数量。
接下来 m 行，每行两个整数 a, b，表示 a 是 b 的"老板"，即 b 向 a 请教了一个问题。
注：无论是否违反了群规，a 都会成为 b 的老板。
很明显，就是有向图判环，但是不可能多一条边判一次，分析可得答案必定是一连串Yes+一连串No
所以可以二分找到 最后一个Yes 然后就解决了。
复习拓扑排序 ：
首先存好自己的手下，然后手下入度++ 。把度数为0的节点入队，然后每次出队 计数器++，
让手下入度-- 如果为0 进队。 最终判断 计数器==总节点数
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=100010; 4 int n,m,in[maxn]; 5 struct node{ 6 int a,b; 7 }stu[maxn<<1]; 8 9 bool ok(int x) { 10 memset(in,0,sizeof(in)); 11 //vector<vector<int> > t(n); 12 vector<int> t[maxn] 13 for(int i=0;i<x;i++) { 14 t[stu[i].a].push_back(stu[i].b); 15 in[stu[i].b]++; 16 } 17 int tot=0; 18 queue<int> q; 19 for(int i=1;i<=n;i++) { 20 if(!in[i]) q.push(i); 21 } 22 while(!q.empty()) { 23 int u=q.front(); 24 q.pop(); 25 tot++; 26 for(int i=0;i<t[u].size();i++) { 27 if(--in[t[u][i]]==0) 28 q.push(t[u][i]); 29 } 30 } 31 return tot==n; 32 } 33 34 int main() { 35 scanf("%d%d",&n,&m); 36 for(int i=0;i<m;i++) { 37 scanf("%d%d",&stu[i].a,&stu[i].b); 38 } 39 int l=1,r=m,ans; 40 while(l<=r) { 41 int mid=(l+r)>>1; 42 if(ok(mid)) { 43 l=mid+1; 44 ans=mid; 45 } else r=mid-1; 46 } 47 for(int i=0;i<ans;i++) printf("Yes\n"); 48 for(int i=ans;i<m;i++) printf("No\n"); 49 return 0; 50 }