本文共 744 字，大约阅读时间需要 2 分钟。

【题目】

【题解】

题目显然是判断有向无环图，有环即输出No。因为要全部人遵守规则才输出Yes，所以答案一定是一连串的Yes后再有一连串的No。判断有无环的存在，无向图可以用并查集，有向图可以用拓扑排序。

n个顶点，m条边，拓扑排序的时间复杂度为O(n+m)，每输入一条边就拓扑排序依次查找肯定超时，所以用到二分。

【代码】

#include 
   
    using namespace std;const int maxn=1e5+5;struct p{    int x,y;}f[2*maxn];vector 
    
      vec[maxn];queue 
     
       q;int in[maxn];int n,m,i;bool check(int x){    for(i=1;i<=n;i++)        vec[i].clear(),in[i]=0;    for(i=1;i<=x;i++)    {        vec[f[i].x].push_back(f[i].y);        in[f[i].y]++;    }    for(i=1;i<=n;i++)        if(!in[i]) q.push(i);    while(!q.empty())    {        int x=q.front(); q.pop();        for(i=0;i
      
       >1;        if(check(mid))        {            r=mid-1;            ans=mid;        }        else l=mid+1;    }    for(i=1;i
      
     
    
   

转载地址：http://nfben.baihongyu.com/