题目概述

有 $n$ 个黑帮首领，每人持枪瞄准另一个首领（可能是自己）。如果发生枪战，规则如下：

• 按某个顺序依次开枪，每人只能开一枪
• 被击中者立即死亡，无法开枪
• 即使目标已死，也必须向原目标开枪（但不会增加死亡人数）
• 不能改变瞄准目标

需要计算在所有可能的开枪顺序下，死亡人数的最小值和最大值。

---

问题分析

关键观察

1. 图论模型：将首领看作点，瞄准关系看作有向边，形成功能图（每个点出度为1）
2. 环与链：功能图由若干环和连向环的链组成
3. 死亡条件：一个首领死亡当且仅当：
   • 他被某人击中（在开枪顺序中，瞄准他的人先于他开枪）
   • 或者他瞄准的人已死，他必须对尸体开枪（浪费子弹）

问题转化

我们需要找出在所有可能的开枪顺序下：

• 最少会有多少人死亡
• 最多会有多少人死亡

---

算法思路

步骤1：拓扑排序处理链部分

对于不在环上的点（即入度为0的点）：

• 它们构成指向环的链
• 这些点一定不会死（因为没人瞄准它们）
• 但它们可能会杀死环上的点

步骤2：处理环

环是问题的核心。对于每个环：

• 最大死亡人数：环上所有人都可能死
• 最小死亡人数：需要精心安排开枪顺序来尽量减少死亡

具体算法

数据结构

• s[i]：首领 $i$ 瞄准的目标
• indeg[i]：入度，用于拓扑排序
• vis1[i]：标记是否在最小死亡方案中死亡
• vis2[i]：标记是否在最大死亡方案中死亡

拓扑排序 (toposort)

void toposort() {
    queue<int> q;
    // 入度为0的点入队（链的起点）
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);
    
    while (!q.empty()) {
        int u = q.front(), v = s[u];
        q.pop();
        
        if (!vis1[u]) vis1[v] = true;  // u没死，v会死（最小方案）
        vis2[v] = true;                // v会死（最大方案）
        
        if (--indeg[v] == 0) q.push(v);
    }
}

拓扑排序的作用：

• 处理所有链上的点
• 确定链上点对环上点的影响

环处理 (solve)

对于每个环：

void solve(int p) {
    // 自环特判
    if (s[p] == p) {
        vis1[p] = vis2[p] = true;
        return;
    }
    
    // 第一遍遍历：找到关键点，标记vis2
    int tmp = p, pos = vis1[p] ? p : 0;
    p = s[p];
    while (p != tmp) {
        indeg[p] = 0;
        if (vis1[p]) pos = p;
        if (vis2[p]) vis2[tmp] = true;
        vis2[p] = true;
        p = s[p];
    }
    
    // 第二遍遍历：确定最小死亡方案
    if (pos) p = pos;
    bool flag = !vis1[p];
    tmp = p, p = s[p];
    while (p != tmp) {
        if (vis1[p]) flag = false;
        else if (flag) {
            vis1[p] = true;
            flag = false;
        } else flag = true;
        p = s[p];
    }
    if (flag) vis1[p] = true;
}

最小死亡人数的策略

在环上，我们可以通过精心安排开枪顺序来救一些人：

• 如果环长 $l$ 为奇数：最少死亡 $\lceil l/2 \rceil$ 人
• 如果环长 $l$ 为偶数：最少死亡 $l/2$ 人
• 但还要考虑链对环的影响

最大死亡人数的策略

在环上，最坏情况下所有人都可能死亡：

• 安排开枪顺序使得每个活着的人都要对尸体开枪
• 但有些点可能因为链的影响而必死或必活

---

样例解析

样例输入

8
2 3 2 2 6 7 8 5

瞄准关系：1→2, 2→3, 3→2, 4→2, 5→6, 6→7, 7→8, 8→5

图结构：

• 环1：2↔3（长度2）
• 环2：5→6→7→8→5（长度4）
• 链：1→2, 4→2

计算结果

• 最小死亡：3人
• 最大死亡：5人

验证：

• 最小：可以救环2中的2人，环1中的1人
• 最大：环上所有人都可能死，加上部分链上点

---

复杂度分析

• 时间复杂度：$O(n)$
  • 拓扑排序：每个点入队一次
  • 环处理：每个环遍历两次
• 空间复杂度：$O(n)$
  • 存储图和相关数组

---

算法亮点

1. 图论建模：将问题转化为功能图分析
2. 分离处理：分别处理链和环的部分
3. 贪心策略：在环上通过交替选择来最小化死亡
4. 拓扑排序：高效处理链对环的影响

---

总结

这道题的核心在于理解功能图的结构，并分别处理链和环：

1. 链处理：拓扑排序确定链上点的生死和它们对环的影响
2. 环处理：精心安排开枪顺序来最小化死亡人数
3. 最大死亡：考虑最坏情况下的开枪顺序
4. 高效算法：线性时间解决大规模数据

这种"功能图分析 + 环链分离"的思路在解决依赖关系问题时非常有效，特别是在每个点只有单一出边的情况下。