很容易看出是拓扑 但不容易想出来怎么做【可能是我太菜
首先 入度为零的人是肯定死不了的
接着 我们分成环和链分析
对于一个链
最多的情况就是顺着一个个开枪 最后剩一个( (n - 1) -> (n), (n - 2) ->(n - 1) …… )
最少的情况就是死一半（1->2, 3->4……）
对于一个环
它和链基本上一样
区别在于从任何一个人开始都不会影响结果
这个性质很有用
因为当有环接在链上时
最多的情况下环上的点会全部挂掉
void bfs(){
for(int i = ; i <= n; i++)
if(!ind[i]){
q[++ans1] = i;
ans2++;
}
for(int i = ; i <= ans1; i++){
int fro = aim[q[i]];
if(vis[fro]) continue;
ind[aim[fro]]--;
vis[fro] = ;
otd[aim[fro]] = ;
if(!ind[aim[fro]]) q[++ans1] = aim[fro];
}//删链过程 非常重要！
for(int i = ; i <= n; i++)
if(!vis[i] && ind[i]){
int len = , flag = ;
for(int j = i; !vis[j]; j = aim[j]){
vis[j] = ;
len++;
flag |= otd[j];
}
//printf("%d %d\n", flag, len);
ans1 += (len >> );
if(len > && !flag) ans2++;
}
}
关键部分