记录编号	421433	评测结果	AAAAAAAAAA
题目名称	膜法师	最终得分	100
用户昵称	licone	是否通过	通过
代码语言	C++	运行时间	1.019 s
提交时间	2017-07-06 20:16:24	内存使用	44.19 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<queue>
using namespace std;

const int N=1000005;

int n,x,a[N],du[N],maxx,minn,c[N],cnt,num[N],num0[N],tot1,fi[N],w[N<<1],ne[N<<1],FI[N];
bool b[N],vis[N];

queue<int> q;

int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

void add(int u,int v)
{
	w[++cnt]=v;ne[cnt]=fi[u];fi[u]=cnt;du[u]++;
	w[++cnt]=u;ne[cnt]=fi[v];fi[v]=cnt;
}

void dfs(int u,int fa)
{
	c[u]=cnt;num[cnt]++;b[u]=1;
	for(int i=fi[u];i;i=ne[i])
	  if(!b[w[i]] && w[i]!=fa && w[i]!=u) dfs(w[i],u);
}

bool che(int u,int siz)
{
	int z=a[u],now=1;
	while(z!=u && now<siz) z=a[z],now++;
	return z==u && now==siz;
}

int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	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__));
	n=read();
	for(int i=1;i<=n;i++) a[i]=read(),add(a[i],i);cnt=0;
	for(int i=1;i<=n;i++) if(!b[i]) cnt++,dfs(i,0),FI[cnt]=i;
	for(int i=1;i<=n;i++) if(!du[i]) num0[c[i]]++;
	for(int i=1;i<=cnt;i++)
	  if(num[i]==1) maxx++;
	  else if(che(FI[i],num[i])) maxx+=num[i]-1;
	  else maxx+=num[i]-num0[i];
	for(int i=1;i<=n;i++) if(!du[i]) q.push(i);
	memset(b,0,sizeof(b));
	while(!q.empty())
	{
		int k=q.front();q.pop();vis[k]=1;k=a[k];
		if(vis[k]) continue;
		b[k]=vis[k]=1;minn++;
		du[a[k]]--;
		if(!du[a[k]]) q.push(a[k]);
	}
	for(int i=1;i<=n;i++)
	  if(!vis[i])
	  {
	  	x=i;tot1=0;
	  	while(!vis[x])
	  	{
	  		vis[x]=1;tot1++;x=a[x];
	  	}
	  	minn+=(tot1+1)/2;
	  }
	printf("%d %d\n",minn,maxx);
	return 0;
}