牛客寒假算法基础集训营4 F(二分+拓扑判环)

时间：2020-12-10 16:21:37

题目链接

题目的输出：对于每次提问，输出一行"Yes"表示大家都遵守了群规，反之输出"No"。

那么输出的就是一连串的yes和no了，二分一下无环的最大提问位置即可，用拓扑check一下就行。

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <math.h>

#include <bitset>

#include <vector>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#define MAXN 1010100

#define LL long long

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define ll __int64

#define INF 0x7fffffff

#define cs(s) freopen(s,"r",stdin)

#define mem(x) memset(x,0,sizeof(x))

#define PI acos(-1)

#define eps 1e-10

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int lcm(int a,int b){return a/gcd(a,b)*b;}

LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

//head

int n,m;

struct uzi

{

	int s,t;

}p[200001];

int d[100001];

vector<int>v[100001];

int ch(int k){

	memset(d,0,sizeof(d));

	for(int i=1;i<=n;i++)v[i].clear();

	for(int i=1;i<=k;i++)d[p[i].t]++,v[p[i].s].pb(p[i].t);

	queue<int>q;

	while(!q.empty())q.pop();

	for(int i=1;i<=n;i++)if(!d[i])q.push(i);

	while(!q.empty()){

		int now=q.front();

		q.pop();

		for(int k:v[now]){

			if(--d[k]==0)q.push(k);

		}

	}

	for(int i=1;i<=n;i++)if(d[i])return 0;

	return 1;

}

int main(){

	ios::sync_with_stdio(false);

	cin>>n>>m;

	for(int i=1;i<=m;i++)cin>>p[i].s>>p[i].t;

	int l=1,r=m,ans=0;

	while(l<=r){

		int mid=(l+r)/2;

		if(ch(mid))ans=mid,l=mid+1;

		else r=mid-1;

	}

	for(int i=1;i<=ans;i++)cout<<"Yes\n";

	for(int i=ans+1;i<=m;i++)cout<<"No\n";

	return 0;

}

相关文章