有n个人，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死的人也不同。

输入n人数<1000000 每个人的aim

你要求最后死亡数目的最小和最大可能

8
2 3 2 2 6 7 8 5

3 5

 

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define N 1000100

 using namespace std;

 int n,cnt;

 int a[N];

 int du[N];

 int head[N];

 int vis[N];

 int v[N];

 int fir[N];

 struct node

 {

     int from,to,next;

 }edge[N<<];

 int belong[N];

 int cnt_du[N];

 int siz[N];

 int tot;

 void init()

 {

     memset(head,-,sizeof(head));

     cnt=;

 }

 void edgeadd(int from,int to)

 {

     edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];

     head[from]=cnt++;

 }

 void dfs(int now,int ff)

 {

     vis[now]=,belong[now]=tot,siz[tot]++;

     for(int i=head[now];i!=-;i=edge[i].next)

     {

         int to=edge[i].to;

         if(to==now||to==ff||vis[to])continue;

         dfs(to,now);

     }

 }

 int check(int now,int num)

 {

     v[now]=;

     int t=now,cntt=;

     while(!v[a[t]])

     {

         v[a[t]]=;

         t=a[t];

         cntt++;

     }

     t=a[t];

     if(t==now&&cntt==num)return ;

     return ;

 }

 int main()

 {

     init();

     scanf("%d",&n);

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

     {

         scanf("%d",&a[i]);

         du[a[i]]++;

         edgeadd(i,a[i]);

         edgeadd(a[i],i);

     }

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

     {

         if(!vis[i])

             tot++,dfs(i,),fir[tot]=i;

     }

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

     {

         if(du[i]==)cnt_du[belong[i]]++;

     }

     int ansma=,ansmi=;

     for(int i=;i<=tot;i++)

     {

         if(siz[i]==)ansma++;

         if(check(fir[i],siz[i]))

             ansma+=siz[i]-;

         else ansma+=siz[i]-cnt_du[i];

     }

     memset(v,,sizeof(v));

     memset(vis,,sizeof(vis));

     queue<int>q;

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

     {

         if(!du[i])

             q.push(i);

     }

     while(!q.empty())

     {

         int u=q.front();

         q.pop();

         v[u]=;

         if(!vis[a[u]])

         {

             v[a[u]]=vis[a[u]]=,ansmi++;

             du[a[a[u]]]--;

             if(!du[a[a[u]]])

                 q.push(a[a[u]]);

         }

     }

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

     {

         if(!v[i])

         {

             int t=i,cnt=;

             while(!v[t])

             {

                 v[t]=;

                 cnt++;

                 t=a[t];

             }

             ansmi+=(cnt+)/;

         }

     }

     printf("%d %d\n",ansmi,ansma);

 }