欧拉回路

看来脑瓜子还是不够灵活啊。以前看到“matching”、“bipartite”一类的标签，试图二分图时只晓得将题目中同一类的元素转化为点，将相对关系转化为边。但实际上，二分图也可以表示其他的二元逻辑关系，例如包含、排除。

例如[NOIP2010 提高组] 关押罪犯，一个经典做法是将罪犯转化为点集，将冲突关系符合一定条件的相互连边，然后二分答案作二分图匹配。（扩展域并查集实质上也是在贪心的基础上，运用“二分图匹配”的思想检查方案合法性……对吧？）

再例如AtCoder ABC 228 G – Digits on Grid，计数DP的转移也是在行、列元素分别作为左部、右部，以方格中的元素作为边权的二分图上进行的。

这道题则非常精妙——CF1634E – Fair Share。看到“要将所有元素分成两个相等的可重集”时，我认为应当用可重集作为二分图的左部和右部。但是这样一来，如何进行匹配呢？正解则是将数组$i$包含元素$a_i$的逻辑关系转化为边——左部为各个数组，右部为相同的元素。可以发现，能够有解的充分必要条件是“每个元素均统共出现了偶数次”，同时“每个数组含有偶数个元素”，那么该图中每个节点的度数均为偶。记得小学奥数的一笔画问题么？它有一个更专业的术语，曰欧拉回路。事实上，一张无向图存在欧拉回路，当且仅当不存在度数为奇的节点。所以，我们直接求解一条欧拉回路，将从左部到右部遍历的边记作$L$，从右部到左部遍历的边记作$R$，就是一个正确的解。