问题分析

这是一个双人不完全信息博弈问题：

• 脑 选择移动哪个棋子
• 蹄 选择具体走哪条出边
• 两个棋子不能重合
• 脑 的目标是让 蹄 无路可走
• 蹄 的目标是让游戏无限进行

关键是不对称的玩家角色：脑有选择权但蹄控制具体移动。

---

关键观察

1. 状态表示

游戏状态可以用 $(u,v)$ 表示，其中 $u$ 和 $v$ 是两个棋子的位置，$u \neq v$。

2. 必败状态分析

一个状态 $(u,v)$ 对 脑 是必败的（即 蹄 获胜），当且仅当：

• 从 $u$ 和 $v$ 出发，蹄总能避免进入死胡同
• 更精确地说：存在策略使得无论脑选择移动哪个棋子，蹄都能让游戏无限继续

3. 简化问题

由于状态空间太大 ($O(N^2)$)，直接分析不可行。需要发现问题的特殊结构。

---

核心解法

1. 单棋子分析

首先考虑只有一个棋子的情况：

• 如果棋子在一个出度为 0 的节点，蹄立即失败（脑获胜）
• 如果棋子在一个环上，蹄可以让游戏永远继续
• 更一般地，如果棋子能到达一个环，蹄可以无限继续

2. 双棋子交互

对于两个棋子 $(u,v)$：

• 如果 两个 棋子都能无限继续（即都能到达某个环），那么蹄获胜（H）
• 如果 至少一个 棋子会必然进入死胡同，那么脑可以通过总是移动那个棋子来获胜（B）

3. 形式化定义

定义 $f(u)$ 表示从节点 $u$ 出发，蹄是否能无限继续游戏。

$f(u) = \text{true}$ 当且仅当：

• $u$ 的出度 > 0，且
• 存在一条从 $u$ 出发的无限路径（即 $u$ 在某个强连通分量中，且该分量不是单个无出边的点）

4. 实际判断方法

通过图分析来判断 $f(u)$：

1. 找出所有终态节点（出度为 0 的节点）
2. 反向传播：如果一个节点的所有出边都指向必败状态，那么该节点也是必败的
3. 剩下的节点就是可以无限继续的

具体算法：

• 计算强连通分量（SCC）
• 将图缩点为 DAG
• 在 DAG 上从出度为 0 的节点开始反向 BFS，标记所有会导致失败的节点
• 剩下的节点就是 $f(u) = \text{true}$ 的节点

5. 最终判断

对于查询 $(x,y)$：

• 如果 $f(x) = \text{true}$ 且 $f(y) = \text{true}$，输出 H（蹄获胜）
• 否则输出 B（脑获胜）

---

为什么这样是正确的？

证明思路：

如果两个棋子都能无限继续：

• 蹄的策略：当脑选择一个棋子时，蹄沿着能无限继续的路径移动
• 由于两个棋子都能独立无限继续，蹄总能避免重合（因为有选择权）
• 因此游戏可以无限进行

如果至少一个棋子不能无限继续：

• 脑的策略：总是移动那个会进入死胡同的棋子
• 蹄虽然可以选择具体路径，但最终那个棋子会进入死胡同
• 当那个棋子无路可走时，蹄失败

---

算法步骤

1. 建图：读入有向图
2. SCC 分解：使用 Tarjan 或 Kosaraju 算法
3. 构建 DAG：将 SCC 缩点
4. 标记失败节点：
   • 初始化：所有出度为 0 的 SCC 标记为失败
   • 反向传播：如果一个 SCC 的所有出边都指向失败 SCC，则标记为失败
5. 处理查询：对于每个 $(x,y)$，检查 $x$ 和 $y$ 所在的 SCC 是否都不是失败 SCC

---

复杂度分析

• SCC 分解：$O(N + M)$
• DAG 构建和标记：$O(N + M)$
• 查询处理：$O(Q)$
• 总复杂度：$O(N + M + Q)$，适合 $N \le 10^5$ 的数据范围

---

总结

这道题的关键在于：

1. 问题转化：将双棋子博弈转化为单棋子的可达性分析
2. 洞察玩家策略：脑的目标是迫使进入死胡同，蹄的目标是保持活跃
3. 图论分析：使用 SCC 和 DAG 来高效判断无限可继续性
4. 简化状态空间：从 $O(N^2)$ 状态降到 $O(N)$ 预处理

通过深入分析游戏机制和图论性质，将复杂的博弈问题转化为高效的图算法问题，体现了竞赛题目中常见的"通过洞察简化问题"的解题思路。