题目大意

有 $N$ 个玩家，每个玩家指控另一个玩家。已知：

平民可能指控任何人（暴徒或平民）

暴徒只会指控平民（不会指控其他暴徒）

求在所有可能的身份分配中，暴徒数量的最大值。

算法思路

核心观察

将玩家视为节点，指控关系视为有向边，则整个图由若干基环树（每个连通分量是一个环，环上挂一些树）组成。

关键性质：

暴徒不能指控暴徒

因此，如果 $u$ 是暴徒，那么 $u$ 指控的人一定是平民

贪心策略

处理树部分（非环部分）

从所有入度为 $0$ 的节点（叶子）开始

如果 $u$ 入度为 $0$，那么 $u$ 一定是暴徒（否则可以增加暴徒数）

如果 $u$ 是暴徒，那么 $u$ 指控的人 $c[u]$ 一定是平民

标记 $c[u]$ 为平民后，$c[u]$ 的入度减少

处理环部分

剩下的未被访问的节点构成若干个环

在环上，暴徒数最多为环长的一半（向下取整）

因为环上不能有两个相邻的暴徒（否则会出现暴徒指控暴徒的情况）

算法流程

读入数据，建立指控关系图

计算每个节点的入度

从所有入度为 $0$ 的节点开始 DFS，标记暴徒和平民

对剩余的环进行 DFS，每个环最多取一半节点作为暴徒

输出暴徒总数

复杂度分析

时间复杂度：$O(N)$，每个节点访问一次

空间复杂度：$O(N)$，存储图和访问标记

总结

本题是图论与贪心的结合：

图结构分析：识别基环树结构，分别处理树和环

贪心选择：在树部分尽可能多地选择暴徒，在环部分采用间隔选择

约束处理：利用"暴徒不指控暴徒"的条件进行推理

该解法通过 $O(N)$ 的复杂度高效解决了最大独立集问题的变种，体现了图论分析在组合优化问题中的重要作用。