记录编号	537410	评测结果	AAAAAAAAAAA
题目名称	[USACO 5.3] 校园网	最终得分	100
用户昵称	leon	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2019-07-12 10:18:53	内存使用	14.17 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=210;
struct Edge{
	int from,to,next;
}e[maxn*maxn];
int head[maxn],low[maxn],dfn[maxn],c[maxn],belong[maxn],c2[maxn],rdu[maxn],cdu[maxn];
bool flag[maxn];
stack<int> q;
int len,Time,num;
void add(int x,int y){
	len++;
	e[len].from=x;
	e[len].to=y;
	e[len].next=head[x];
	head[x]=len;
}
void tarjan(int x){
	q.push(x); Time++; dfn[x]=Time; low[x]=Time; flag[x]=1;
	for(int i=head[x];i!=-1;i=e[i].next){
		int j=e[i].to;
		if(dfn[j]==0){
			tarjan(j); low[x]=min(low[x],low[j]);
		}
		else if(flag[j]) low[x]=min(low[x],dfn[j]);
	}
	if(dfn[x]==low[x]){
		int k;num++;
		do{
			k=q.top();
			belong[k]=num;
			q.pop();flag[k]=0;
		}while(k!=x);
	}
}
int main(){
	freopen("schlnet.in","r",stdin);
	freopen("schlnet.out","w",stdout);
	memset(head,-1,sizeof(head));
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;
		while(scanf("%d",&x),x){
			add(i,x);
		}
	}
	for(int i=1;i<=n;i++) if(!dfn[i]){
		tarjan(i);
	}
	for(int i=1;i<=len;i++){
		int s=e[i].from,t=e[i].to;
		if(belong[s]==belong[t]) continue;
		rdu[belong[t]]++; cdu[belong[s]]++;
	}
	int ans1=0,ans2=0;
	for(int i=1;i<=num;i++){
		if(rdu[i]==0) ans1++;
		if(cdu[i]==0) ans2++;
	}
	if(num==1){
		printf("%d\n0",ans1);return 0;
	}
	printf("%d\n%d",ans1,max(ans1,ans2));
	return 0;
}