用C语言编写狙击手存活问题

Question

N个狙击手在进行生死搏斗，每位狙击手各瞄准了一个目标，一旦开枪就会将被瞄准的目标消灭，被消灭的狙击手无法再开枪。已知任意两个狙击手不会同时开枪，但不知道他们的开枪顺序，所以无法确定最后哪些狙击手会存活下来。
请你求出最少可能存活多少个狙击手，最多可能存活多少个狙击手。
输入描述:
第一行一个正整数N 接下来一行N个正整数，第i个数字Ti表示第i个狙击手瞄准了第Ti个狙击手，注意可能存在Ti=i

输出描述:
两行，第一行是最少存活的狙击手的数量，第二行是最多存活的狙击手的数量
示例1
输入
8
2 3 2 2 6 7 8 5
输出
3
5
请问该问题用C语言该怎么编呢？

Answer 1

#include<stdio.h>
using namespace std;
#define maxn 1000001
int q[maxn],a[maxn],IN[maxn],die[maxn],undie[maxn];
int n;
int ans1,ans2,len,bo;
int main()
{
int x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);++IN[a[i]];
}
for(int i=1;i<=n;i++)
if(IN[i]==0)
{
++ans1;q[++ans2]=i;
}
for(int i=1;i<=ans2;i++)
{
x=a[q[i]];
if(die[x])continue;
die[x]=1;
undie[a[x]]=1;--IN[a[x]];
if(IN[a[x]]==0)q[++ans2]=a[x];
}
for(int i=1;i<=n;i++)
if(IN[i]&&!die[i])
{
len=bo=0;
for(int j=i;!die[j];j=a[j])
{
die[j]=1;
++len;
bo|=undie[j];
}
if(!bo&&len>1)
++ans1;
ans2+=len/2;
}
printf("%d\n%d",n-ans2,n-ans1);
}