记录编号	318226	评测结果	AAAAAAAAAA
题目名称	膜法师	最终得分	100
用户昵称	LOSER	是否通过	通过
代码语言	C++	运行时间	2.201 s
提交时间	2016-10-09 06:39:53	内存使用	69.93 MiB

/*
  Name: 枪战 
  Author: Loser? 
  Date: 02/10/16 20:24
  Description: 
		考试时被坑了半天 以为是简单的缩点
		但其实是有贪心的感觉
		1>  求最小值
			即活着(入度为零)的人数最多
 			此点肯定活着 所以必须开枪 如果因此 多了一个入度为零的点 则压入队列
			到最后暴力判环即可
		2> 求最大值 
			 也就是 如果是一个点 则为 1
			 如果是一个环 则为 num-1
			 else {
				反向建图 此时为一棵树 (缩完点后)
				即可求解		
			} 
*/
#include<cstdio>
#include<queue>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
#define maxn 1000010
#define MIN(a,b) (a<b?a:b)
int n,d[maxn],to[maxn],rd[maxn];
struct Edge{int to,next,from;}e[maxn<<1],a[maxn];
int lena,heada[maxn],len,head[maxn];
void Addedge(int x,int y){
	e[++len].to=y;
	e[len].from=x;
	e[len].next=head[x];
	head[x]=len;
}
void Insert(int x,int y){
	a[++lena].to=y;
	a[lena].from=x;
	a[lena].next=heada[x];
	heada[x]=lena;	
}
bool Check[maxn];
stack<int> qq;
int low[maxn],Dfn[maxn],Time,cnt,Belong[maxn],num[maxn];
void Dfs(int x){
	Check[x]=1; qq.push(x);
	low[x]=Dfn[x]=++Time; 
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(!Dfn[y]){
			Dfs(y);
			low[x]=MIN(low[y],low[x]);	
		}
		else if(Check[y])low[x]=MIN(Dfn[y],low[x]);
	}
	if(low[x]==Dfn[x]){
		int k; cnt++;
		do{
			k=qq.top();qq.pop();Check[k]=0;
			Belong[k]=cnt; num[cnt]++;
		}while(k^x);
	}
}
int Work(int x,int &tot){
	int temp=0;	
	tot+=num[x];
	for(int i=heada[x];i;i=a[i].next){
		int y=a[i].to;
		if(!d[y]){tot++;temp++;continue;}
		else temp+=Work(y,tot);	
	}	
	return temp;
}
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__));
	queue<int> q;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&to[i]);
		d[to[i]]++; Addedge(to[i],i); 
	}
	for(int i=1;i<=n;i++){
		if(!d[i])q.push(i);	
	}
	while( !q.empty() ){
		int k=q.front(); q.pop();
		int t=to[k];
		if(!Check[t]){
			Check[t]=1;	
			if(--d[to[t]]==0)q.push(to[t]);	
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!Check[i]){
			int x=i,num=0;
			if(Check[to[i]])num=2;
			while(!Check[to[x]]){
				Check[to[x]]=1;
				x=to[x];	
				num++;
			}		
			ans+=num/2;
		}	
	}
	printf("%d ",n-ans);
	memset(Check,0,sizeof(Check));
	for(int i=1;i<=n;i++){
		if(!Dfn[i])Dfs(i);	
	}
	memset(d,0,sizeof(d));
	for(int i=1;i<=len;i++){
		int u=e[i].from,v=e[i].to;
		if(Belong[u]==Belong[v])continue;
		Insert(Belong[u],Belong[v]);	
		d[Belong[u]]++; rd[Belong[v]]++;
	}
	ans=0;
	memset(Dfn,0,sizeof(Dfn));
	for(int i=1;i<=cnt;i++){
		if(!rd[i]){
			int tot=0;
			if(!d[i]){
				if(num[i]==1)ans++;
				else ans+=num[i]-1;
			}
			else{
				int data=Work(i,tot);
				ans+=tot-data;	
			}	
		}
	}
	printf("%d\n",ans);
	getchar(); getchar();
	return 0;	
}