记录编号	137110	评测结果	AAAAAAAAAAA
题目名称	[USACO 5.3] 校园网	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2014-11-04 08:07:20	内存使用	0.40 MiB

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
bool flag[101][101]={0},flag1[101]={0},flag2[101]={0};
int dto[101][101]={0},redto[101][101]={0},bh[101]={0},A[201]={0},insum[101]={0},outsum[101]={0};
int i,j,k=0,l,p,n,m,zj1,zj2,zj3,ans;
void init()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&zj1);
		while(zj1!=0)
		{
			dto[i][++dto[i][0]]=zj1;
			redto[zj1][++redto[zj1][0]]=i;
			scanf("%d",&zj1);
		}
		flag[i][i]=true;
	}
}
void dfs1(int x)
{
	flag1[x]=true;
	for(int h=1;h<=dto[x][0];h++)
	if(!flag1[ dto[x][h] ])
	dfs1(dto[x][h]);
	A[++A[0]]=x;
}
void dfs2(int x)
{
	flag2[x]=true;
	bh[x]=k;
	for(int h=1;h<=redto[x][0];h++)
	if(flag1[ redto[x][h] ]&&!flag2[ redto[x][h] ])
	dfs2(redto[x][h]);
}
void Connectwork()
{
	for(i=1;i<=n;i++)
	if(!flag1[i])
	{
		A[0]=0;
		dfs1(i);
		for(j=A[0];j>0;j--)
		if(!flag2[A[j]])
		k++,dfs2(A[j]);
	}
}
void findwork()
{
	for(i=1;i<=n;i++)
	for(p=1;p<=dto[i][0];p++)
	if(!flag[ bh[i] ][ bh[ dto[i][p] ] ])
	{
		flag[ bh[i] ][ bh[ dto[i][p] ] ]=true;
		outsum[ bh[i] ]++;
		insum[ bh[ dto[i][p] ] ]++;
	}
	zj1=0;zj2=0;
	for(i=1;i<=k;i++)
	{
		if(insum[i]==0)zj1++;
		if(outsum[i]==0)zj2++;
	}
	printf("%d\n",zj1);
	if(zj1<zj2)ans=zj2;
	else ans=zj1;
	if(k==1)ans=0;
	printf("%d\n",ans);
}
int main()
{
	freopen("schlnet.in","r",stdin);
	freopen("schlnet.out","w",stdout);
	init();
	Connectwork();
	findwork();
	return 0;
}