哈希与随机-题目

P8819 [CSP-S 2022] 星战

考虑本题需要判断的是每个点的出度是否都为 $1$。

首先每个状态时总边数时容易计算的。那么接下来只要判断是否每个节点的出度都是奇数。

每个元素的奇偶性的判断，容易想到哈希。对每一个点赋一个随机权值，统计当前状态下所有出度的权值异或和，这也是容易的。

如果异或和不等于所有点的权值异或和，那么答案是 NO。