记录编号	318339	评测结果	AAAAAAAAAA
题目名称	膜法师	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.999 s
提交时间	2016-10-09 09:27:21	内存使用	14.62 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
const int maxn = 1e6 + 10;

#define is_num(x) (x <= '9' and x >= '0')
inline int get_num() {
	char tmp = getchar();
	int res = 0;
	
	while (not is_num(tmp)) tmp = getchar();
	while (    is_num(tmp)) {
		res = (res << 3) + (res << 1) + tmp - '0';
		tmp = getchar();
	}
	
	return res;
} 

int in[maxn], to[maxn];
int de[maxn];
int del, min_ans;
int n;

inline void read() {
	n = get_num();
	for (int i = 1; i <= n; i++) {
		to[i] = get_num();
		in[to[i]]++;
	}
}

bool instack[maxn];
bool vis[maxn], use[maxn];

void dfs(int now) {
	vis[now] = true, instack[now] = true;
	int tar = to[now];
	
	if (instack[tar]) del++;
	if (vis[tar]) return;
	
	dfs(tar);
	instack[now] = false;
}

inline void solve() {
	for (int i = 1; i <= n; i++) if (not in[i]) dfs(i);
	del = 0;
	for (int i = 1; i <= n; i++) if (not vis[i] and to[i] != i) dfs(i);
	
	memset(vis, 0, sizeof(vis));
	queue <int> q;
	for (int i = 1; i <= n; i++) {
		if (not in[i]) {
			del++;
			q.push(i);
			vis[i] = true;
		}
	}
	
	while (not q.empty()) {
		int now = q.front(); q.pop();
		int tar = to[now];
		
		if (use[tar]) continue;
		vis[tar] = use[tar] = true, min_ans++;
		if (--in[to[tar]]) continue;
		q.push(to[tar]);	
	}
	
	int now, tar;
	for (int i = 1; i <= n; i++) {
		if (vis[i]) continue;
		
		now = i;
		while (true) {
			tar = to[now];
			if (vis[tar]) break;
			
			vis[tar] = true, min_ans++;
			
			now = to[tar];
			if (vis[now]) break;
		}
	}
	
	printf("%d %d\n", min_ans, n - del);
}

int main() {
	freopen("maf.in", "r", stdin);
	freopen("maf.out", "w", stdout);
	int __size__= 128 << 20;
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	read();
	solve();
	return 0;
}