D. Robot Rapping Results Report(拓扑排序+二分)

问题有明显的单调性,考虑每次用拓扑排序检验正确性

$Ⅰ.如果拓扑排序结束,还有点没被入队过,说明有环,有环是无法确定的$

$Ⅱ.每次删掉一个点后,会把周围点的入度减减,但是一次最多只有一个点入度变成0.$

$如果多于这个数,那么这几个点处于同一层级,无法判断能力强弱$

//怎样能确定?
//一、没有环
//二、只有一个入度为1的点
//三、每次只会加入一个点
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10; 
int n,m,l[maxn],r[maxn],in[maxn];
vector<int>vec[maxn];
bool tuopu()
{
	queue<int>q;
	int temp=0;
	for(int i=1;i<=n;i++)
		if( in[i]==0 )	temp++,q.push(i);
	if( temp!=1 )	return false;	
	while( !q.empty() )
	{
		int u=q.front(),lin=0; q.pop();
		for(int i=0;i<vec[u].size();i++)
		{
			int v=vec[u][i];
			if( --in[v]==0 )	q.push(v),temp++,lin++;
		}
		if( lin>1 )	return false;
	}
	if( temp!=n )	return false;
	return true;
} 
void init(int mid)
{
	for(int i=1;i<=n;i++)	vec[i].clear(),in[i]=0;
	for(int i=1;i<=mid;i++)
	{
		vec[ r[i] ].push_back( l[i] );
		in[ l[i] ]++;
	}
}
int main()
{
	cin >> n >> m;
	for(int i=1;i<=m;i++)
		scanf("%d%d",&l[i],&r[i]);
	int L=1,R=m,mid,ans=-1;
	while( R>=L )
	{
		mid=L+R>>1;
		init(mid);
		if( tuopu() )	R=mid-1,ans=mid;
		else	L=mid+1;
	}
	cout << ans;
} 

最后

以上就是傻傻小猫咪为你收集整理的D. Robot Rapping Results Report(拓扑排序+二分)的全部内容，希望文章能够帮你解决D. Robot Rapping Results Report(拓扑排序+二分)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。