作业之考试n

作业之考试n
首先,我们知道每个人只能告诉一个人(一个出度),却能被几个人告知(入度不定)。
结论1:入度为0的人不可能从他人那里知道自己生日;
结论2:假如入度为1的人的那个“1”入度为0,那么他也不可能从他人那里知道自己生日。
所以我们先把所有入度为0的人排除,以及让被排除的人的告诉的人的入度减一,直到没有入度为0的人;
又因为每个人只有一个出度,那么剩下的人的告知关系一定会变成几个环;然后就只统计每个环就行了,但是数据大了这种方法还是会超时。

#include<bits/stdc++.h>
using namespace std;
int m=9999999,n;
int ha[200010],kao[200010];
int sf(int st,int hahaha){
	kao[st]=0;
	if(st==kao[0]) return hahaha;
	else return sf(ha[st],hahaha+1);
}
int main(){
//	freopen("message.in","r",stdin);
//	freopen("message.out","w",stdout);
	int q[200010]={0},w[200010];
	scanf("%d",&n);
	for(int z=1;z<=n;++z){
		scanf("%d",&ha[z]);
		++kao[ha[z]];
	}
	for(int z=1;z<=n;++z)
		if(!kao[z])
			q[++q[0]]=z;
	kao[0]=1;
	while(1){
		if(kao[0]&1){
			w[0]=0;
			for(int z=1;z<=q[0];++z){
				--kao[ha[q[z]]];
				if(!kao[ha[q[z]]]){
					kao[0]=2;
					w[++w[0]]=ha[q[z]];
				}
			}
			if(!w[0]) break;
		}
		else{
			q[0]=0;
			for(int z=1;z<=w[0];++z){
				--kao[ha[w[z]]];
				if(!kao[ha[w[z]]]){
					kao[0]=1;
					q[++q[0]]=ha[w[z]];
				}
			}
			if(!q[0]) break;
		}
	}
	for(int z=1;z<=n;++z)
		if(kao[z]){
			kao[0]=z;
			m=min(m,sf(ha[z],1));
		}
	printf("%d",m);
}
上一篇:【HDU5840】This world need more Zhu


下一篇:[HDU2460]Network