BZOJ 2438 中山市选2011 杀人游戏的题解及分析

（这个多年前的文章发现一直未通过，现在修改一下再补发出来）

【分析】：

提示：在正文下方，附了几个数据

这道题可以通过求解强连通分量来完成分析。基于题目要求，在本问题中我们主要关注第一位参与者是否是杀手：如果他是，则按照问题描述的规定情况，则警察会被立即消灭；反之，则警察无法在游戏结束前被消灭，并且题目中的条件说明了这一点。

第一步, 将每对关系<x,Y>表示为边x-y的存在; 然后, 使用 Tarjan 算法计算各节点间的强 连通 分量, 将每个 强 连 通 分 量 简 化 为 单一 节 点, 并 记录 各 节 点 所 属 Strongly Connected Component（SCC）之间的 入 度 关系. 接着, 统计所有 SCC 中人 入 度 为空 的 类 别 数目, 这即 表示 需要 访问 的 最小 快 数. 但 是, 针 对 后续 测试 数据集中的情况, 当某个 SCC 的 入 度 为空且仅包含单个节点时, 我们需要减少整体所需块数的数量. 不幸的是, 这种情况仍无法完全覆盖所有测试用例. 因此, 在某些特定情况下需要对该优化策略施加限制条件: 即当前所需块数超过一个的情况下实施这一优化策略.

【数据】：

3 1
1 2 ans:0.666667

5 8
1 2
2 1
2 3
3 2
3 4
4 3
1 4
4 1