题目背景

浙江省的几所OI强校的神犇发明了一种人工智能，可以AC任何题目，所以他们决定建立一个网络来共享这个软件。但是由于他们脑力劳动过多导致全身无力身体被♂掏♂空，他们来找你帮助他们。

题目描述

共有n所学校（n<=10000）已知他们实现设计好的网络共m条线路，为了保证高速，网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机母鸡，能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机母鸡都可以使别的学校使用上软件。

输入输出格式

输入格式：

第一行一个整数n。

接下来n行每行有若干个整数，用空格空格隔开。

第i-1行的非零整数x，表示从i到x有一条线路。以0作为结束标志。

输出格式：

第一行一个整数表示问题1的答案。

第二行回答问题2.

输入输出样例

5
2 0
4 0
5 0
1 0
0

2
2

说明

POJ原题。数据扩大了100倍。

        本来这道题用Tarjan就能简单过了，但是为了研究传说中的可真辣鸡Kosaraju算法还是重新写了一遍。感谢WKL大神的博客，链接放在这里：http://wuvin.lofter.com/post/1dcf22f2_9dca761

#include<cstdio>
#include<cstring>
#include<queue>
#define max(a, b) (a > b ? a : b)
using namespace std;
const int maxn = 1e4 + 100;
const int maxm = 1e6 + 100;
struct edge {
	int v, next;
}e[maxm];
int cnt, n, ltcnt = 1;
int head[maxn], connect[maxn];
int indg[maxn], outdg[maxn];
bool vis[maxn];
inline void adde(const int &u, const int &v) {
	e[cnt] = (edge) {v, head[u]};
	head[u] = cnt++;
}
queue<int > q;
void dfs1(int u) {
	if(vis[u]) return ;
	vis[u] = 1;
	for(register int i = head[u]; i != -1; i = e[i].next) {
		int v = e[i].v;
		dfs1(v);
	}
	q.push(u);
}
void dfs2(int u, int ltcnt) {
	if(vis[u]) return ;
	vis[u] = 1;
	connect[u] = ltcnt;
	for(int i = head[u]; i != -1; i = e[i].next) {
		int v = e[i].v;
		dfs2(v, ltcnt);
	}
}
void topsort() {
	for(register int i = 1; i <= n; ++i)
		if(!vis[i])
			dfs1(i);
}
void kozaraju() {
	topsort();
	memset(vis, 0, sizeof(vis));
	while(!q.empty()){
		int v = q.front();
		if(!vis[q.front()])
			dfs2(q.front(), ltcnt++);
		q.pop();
	}
}
int main() {
	memset(head, -1, sizeof(head));
	scanf("%d", &n);
	int a = 0;
	for(register int i = 1; i <= n; ++i) {
		while(1){
			scanf("%d", &a);
			if(!a) break;
			adde(i, a);
		}
	}
	kozaraju();
	for(register int i = 1; i <= n; ++i) 
		for(register int j = head[i]; j != -1; j = e[j].next) 
			if(connect[i] != connect[e[j].v])
				++outdg[connect[i]], ++indg[connect[e[j].v]];
	int inzr = 0, outzr = 0;
	for(register int i = 1; i < ltcnt; ++i) {
		inzr += indg[i] == 0, outzr += outdg[i] == 0;
	}
	printf("%d\n", inzr);
	printf("%d", max(inzr, outzr));
	return 0;
}