这题的“矛盾检测”是典型的扩展域并查集。
但是一个难点是,“裁判”的身份会改变矛盾的判断。如果一局有“裁判”参与,那么这局肯定是合法的。只有任为某一局没有裁判参与,才能通过并查集判断是否合法。
因此直接做会十分困难,我们需要转换为: 枚举裁判 再验证合法性。
当枚举 为裁判时,直接忽略一切 参与的对局。此时如果仍然出现矛盾,那么只能说明 不是裁判或者 不是唯一的裁判,即除了 之外至少有一个人是裁判。
枚举所有的 ,然后记录没有出现矛盾的次数 . 如果 为 ,那么没有人是唯一的裁判,输出 Impossible;如果 大于 ,那么有多个人都可以作为唯一的裁判,输出 Can not determine;只有 恰好为 时,能唯一确定某一个人是唯一的裁判。但这时候,我们需要输出判断所需的”最小轮数“。
这就是最传神的地方:一个轮数 是能够判断 是唯一裁判的最小轮数,意味着在 轮中,足以排除其他人是裁判的可能性,而在 轮中不足以排除其他人是裁判的可能性。
这就是说, 就是枚举所有 的时候,矛盾首次出现的轮数的最大值。