记录编号	432148	评测结果	AAAAAAAAAA
题目名称	膜法师	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.469 s
提交时间	2017-08-02 21:32:05	内存使用	15.57 MiB

#include <stdio.h>
#include <deque>
#define maxn 1000005
using namespace std;
int n,aim[maxn],ru[maxn],maxx,minn,yes[maxn],no[maxn];
deque<int> q;
void push_ru_0(){
     for(int i=1;i<=n;i++)
        if(!ru[i]){
          minn++;maxx++;    
          q.push_back(i);
        }
}
void kill_(){
     for(int i=1;i<=minn;i++){
        int k=aim[q.front()];
        q.pop_front();
        if(yes[k]) continue;
        yes[k]=1;//之后他打死一个人后
        no[aim[k]]=1;
        ru[aim[k]]--;
        if(ru[aim[k]]==0){//看那个人要打的人是否变成了入度为零.
          q.push_back(aim[k]);//如果变成了入度为零那么继续进队。
          minn++;
        }
    }//最后整张图剩下了一堆环。
}
int main(){
	freopen("maf.in","r",stdin);// 原题[POI2008]枪战Maf
	freopen("maf.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&aim[i]);
        ru[aim[i]]++;
    }//首先入度为零的肯定死不了。
    push_ru_0();//然后我们将入度为0的推入队列。
    kill_(); 
    for(int i=1;i<=n;i++){
        if(ru[i]&&!yes[i]){
            int zz=i,lian=0;bool pd=0;
            while(!yes[zz]){
                  yes[zz]=1;zz=aim[zz];lian++;
                  if(no[zz]) pd=1;
            }
            if(!pd&&lian>1) maxx++;//没入度，活一个 
            minn+=lian/2;//没入度，活一半 
        }
    }
    printf("%d %d",n-minn,n-maxx);
}