Description：

给定 $n$ 个神枪手，每个神枪手瞄准一个人，以一定顺序开枪，问最少和最多死多少人。

$1\leqslant n\leqslant 10^6$

Solution：

最多死很好说，如果是一棵树（根是一个自环）那就剩一个（入度为 $0$ 的那个），如果是一个单个的环那就剩一个，如果是一个基环树那就只有叶子节点能剩下。

最少死就很麻烦了，如果是一个序列那就隔着打，如果是一个树或者是一个基环树，那么所有叶子肯定是要留下的，然后叶子瞄准的那个人瞄准的那个人要尽可能让他留下来，因为能多留一个是一个，拿它去换别的点一定只能多获得一个点，但还不一定得的到，然后这样每次入度 $-1$ ，如果入度减为零了就把他入队，实现起来有很多细节。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int f[MAXN];

int ind[MAXN];

bool v[MAXN],vis[MAXN];

void mark(int k)

{

	v[k] = true;

	if(v[f[k]])return;

	mark(f[k]);

	return;

}

int fa[MAXN],siz[MAXN];

int find(int x){return (x == fa[x] ? x : fa[x] = find(fa[x]));}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&f[i]);

	for(int i = 1;i <= n;++i)++ind[f[i]];

	int ans1 = 0,ans2 = 0;

	for(int i = 1;i <= n;++i)

	{

		if(ind[i] == 0)

		{

			mark(i);

			++ans1;

		}

	}

	for(int i = 1;i <= n;++i)siz[i] = 1;

	for(int i = 1;i <= n;++i)fa[i] = i;

	for(int i = 1;i <= n;++i)

	{

		if(!v[i])

		{

			int p = find(i),q = find(f[i]);

			if(p != q)

			{

				fa[p] = q;

				siz[q] += siz[p];

			}

		}

	}

	int res1 = 0,res2 = 0;

	for(int i = 1;i <= n;++i)

	{

		if(!v[i] && !vis[find(i)])

		{

			if(siz[find(i)] != 1)res1 += 1;

			res2 += (siz[find(i)] + 1) / 2;

			vis[find(i)] = true;

		}

	}

	memset(v,false,sizeof(v));

	memset(vis,false,sizeof(vis));

	queue<int> q;

	for(int i = 1;i <= n;++i)

	{

		if(ind[i] == 0)

		{

			q.push(i);

			v[i] = true;

		}

	}

	ans2 = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		if(!v[f[k]])--ind[f[f[k]]];

		v[f[k]] = true;

		++ans2;

		if(ind[f[f[k]]] == 0 && !v[f[f[k]]])

		{

			q.push(f[f[k]]);

			v[f[f[k]]] = true;

		}

	}

	for(int i = 1;i <= n;++i)fa[i] = i;

	for(int i = 1;i <= n;++i)siz[i] = 1;

	int tot = 0;

	for(int i = 1;i <= n;++i)

	{

		if(!v[i])

		{

			++tot;

			int p = find(i),q = find(f[i]);

			if(p != q)

			{

				fa[p] = q;

				siz[q] += siz[p];

			}

		}

	}

	ans1 = n - (res1 + ans1);

	res2 = 0;

	for(int i = 1;i <= n;++i)

	{

		if(!v[i] && !vis[find(i)])

		{

			res2 += (siz[find(i)] + 1) / 2;

			vis[find(i)] = true;

		}

	}

	cout << res2 + (n - tot) - ans2 << " " << ans1 << endl;

	return 0;

}