题目描述
有 n 个人，用1∼n 进行编号，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死的人也不同。
Input
输入
人数 n<1000000
接下来 n 个数，依次为每个人的 aim
Output
输出只有一行，共两个数，为要求最后死亡数目的最小和最大可能。
Sample Input
Sample Output
分析
如果\(a\)瞄准\(b\)，那么我们就从\(a\)到\(b\)建一条有向边
我们设最大存活程度为\(Max\)，最小存活程度为\(Min\)
不难发现，入度为\(0\)的点必定存活（左图中的绿圈）
因为没有人会瞄准他
进一步分析可以发现，建好图后的联通块有两种情况
1、左图（非环）
显然，\(1\)号节点、\(4\)号节点必定存活，而他们所指的\(2\)号节点必死
问题就在\(3\)号节点，如果他先射杀\(2\)号节点，那么他的入度变为\(0\)，存活人数为\(3\)
如果\(2\)号节点先射杀\(3\)，那么三号节点的入度仍为\(1\),存活人数为\(2\)
所以，我们可以向拓扑排序那样维护入度为\(0\)的点，将其放入队列中
队首的目标必死，队首目标的目标可死可不死，打上标记
2、右图（环状）
最小存活：+1（无论如何都会剩一个人）
最大存活：隔一个人打一个，可以最大存活 len/2；
要特别判断自己打自己的环
代码
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1e6+5;
int n,Max,Min,q[maxn],aim[maxn],rd[maxn];
bool die[maxn],undie[maxn];
void Init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&aim[i]);
rd[aim[i]]++;
}
for(int i=1;i<=n;++i)//入度为0的点必活
if(rd[i]==0){
Min++;//最小必活数+1
q[++Max]=i;//队列维护的是入度为0的点
}
}
void Solve(){
int head=1;
while(head<=Max){//扫描队列
int cur=q[head];head++;//取出队首并出队
if(die[aim[cur]]) continue;//队首目标已死(多个入度为0的点指向一个点)
die[aim[cur]]=1;//队首目标必死
int live=aim[aim[cur]];//队首目标的目标可死可不死，看决策
rd[live]--;//
undie[live]=1;//可以让他活，但想死的时候随时可以让他死，在环可以最后死
if(rd[live]==0)//虽然入度为0，但不一定是必活，所以Min不加
q[++Max]=live;
}
//下面处理只剩下环
for(int i=1;i<=n;++i)
if(rd[i] && !die[i]){
int len=0,flag=0;//len记录环大小,flag标记环上是否有undie的点
for(int j=i;!die[j];j=aim[j]){
len++;
flag|=undie[j];
die[j]=1;//标记已死，避免其他的再来计算
}
if(!flag && len>1) Min++;//len=1表示自环，必死
Max+=len/2;
}
printf("%d %d",n-Max,n-Min);
}
int main(){
Init();
Solve();
return 0;
}