题目大意
输入格式
输出格式
数据范围与提示
算法分析
-
设最少存活人数为MIN 最多存货人数为MAX
来看张图：
-
首先我们先来统计一下每个点的入度，如果一个点的入度为0，则自始至终这个人都不可能被杀（
没人想杀小姐姐），就像图里的1和4，所以这个人想杀的人一定会死(震惊) 也就是图中的2 -
每个人都会有想杀的人（咱也不知道为啥会想杀自己），一个人如果入度不为0 ，他想杀的人就不一定会死（为了保护你想杀的小姐姐 先把你干掉）
这样的点的目标就像3，可能会死掉（如果拯救小姐姐的人来晚了，小姐姐就被大魔王煮着吃了）
我们可以发现： -
如果一个点入度为0（绿框） 那么这个点一定会活下来 ：MIN++ MAX++
-
最小存活：让必定会死的人2先把自己要杀的人3杀掉（undie标记3）（在勇士救出小姐姐之前吃了她）则MIN就不能加1了
-
最大存活：先把必定会死的人杀死防止他去杀他要杀的人（勇士在魔王吃掉小姐姐之前干掉大魔王），那么最大存活就会加1了（就像例图中3被解救了）
But 对小姐姐图谋不轨的人远不止一个呢？ 因此我们不能直接判定小姐姐是可以存活的，但是我们可以将小姐姐的入度--
如果入度成功变成了0。 恭喜你，小姐姐得救了（虽然不能和你幸福地生活在一起），我们就可以将这个点入队了（队列维护入度为0的点，表示安全的点） -
但是如果这个点的入度并没有变成0 则这个点一定也会构成一个环或者链 ，关于链显然隔一个人打一个人可以存活最多的人（n/2），存活最少的人就是只活一个（很简单，自己推）
-
如果环上有undie标记的人，可以让这个人最后死，然后在这个环死的只剩他的时候，BOOM 干掉他
-
当然还有一种情况就是直接的无任何undie标记的环 ， 同上
1.最小存活： +1
2.最大存活： +n/2 -
具体的细节去看注释吧
代码展示
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,Max,Min,q[maxn],aim[maxn],rd[maxn];
bool die[maxn],undie[maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&aim[i]);
rd[aim[i]]++;
}
for(int i=1;i<=n;++i)
if(rd[i]==0){//入度为0的点进队
Min++;//最小存活++
q[++Max]=i;//最大存活++
}
int head=1;//模拟指针
while(head<=Max){
int cur=q[head];head++;//队首出队
if(die[aim[cur]]) continue;//如果队首要杀的人已经被别人杀了
die[aim[cur]]=1;//标记队首要杀的人
int live=aim[aim[cur]];//队首目标的目标可死可不死
rd[live]--;//入度--
undie[live]=1;//可以不死了
if(rd[live]==0)//如果入度变为0了
q[++Max]=live;//最大存活数++，入队
}
//下面是处理环的
for(int i=1;i<=n;++i)
if(rd[i] && !die[i]){//如果当前位置入度不为0 并且还没死
int len=0,flag=0;//len为环的长度 flag判定当前人是否可能会死
for(int j=i;!die[j];j=aim[j]){//遍历环
len++;//环长度++
flag|=undie[j];//当前人是否可能会死
die[j]=1;//标记为已死 防止下次i到这个位置再计算
}
if(!flag && len>1) Min++;//如果当前点不可能会死 而且环长度>1(不是自环) ，最小存活数++
Max+=len/2;//最大存活数加上环长度的一半
}
printf("%d %d",n-Max,n-Min);//要输出最小死亡数和最多死亡数
return 0;
}
感谢观看
点个关注>:<