链接：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"。
示例1
输入
4 4 1 2 2 3 3 1 1 4
输出
Yes Yes No No
备注:
1≤n≤1051≤n≤105
1≤m≤2?1051≤m≤2?105
1≤a,b≤n
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<vector> #include<queue> #include<map> #define ll long long #define inf 0x3f3f3f3f using namespace std; const int maxx=1e5+5; int n,m,a,b; int deg[maxx]; vector<int>vec[maxx]; struct node { int a; int b; }; node edge[2*maxx]; queue<int>q; bool tuopu() { while(!q.empty()) q.pop(); for(int i=1;i<=n;i++) if(deg[i]==0) q.push(i); int now;//当前头结点 while(!q.empty()) { now=q.front(); q.pop(); for(int i=0;i<vec[now].size();i++) { if( --deg[ vec[now][i] ]==0 ) q.push(vec[now][i]); } } for(int i=1;i<=n;i++)//检查有没有入度不为0的结点，有的话就是环了 if(deg[i]) return false; return true; } bool check(int x) { memset(deg,0,sizeof(deg)); for(int i=1;i<=n;i++) vec[i].clear(); for(int i=1;i<=x;i++)//建图 { node e=edge[i]; deg[e.a]++; vec[e.b].push_back(e.a); } return tuopu(); } int main() { while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=m;i++) scanf("%d%d",&edge[i].a,&edge[i].b); int l=1,r=m; int mid; int ans; while(l<=r) { mid=(l+r)/2; if( check(mid) ) { ans=mid; l=mid+1; } else { r=mid-1; } } for(int i=1;i<=m;i++) if(i<=ans) printf("Yes\n"); else printf("No\n"); } return 0; } /// a b表示a是b的老板，规定箭头由b指向a，a的入度+1，a←b,b的邻接表压入a