ARC161E Not Dyed by Majority (Cubic Graph)

· · 个人记录

给出一个每个点度数为3的简单无向图，将点黑白染色，然后同时替换成相邻点颜色的众数。问是否存在某个无法得到的颜色序列，构造方案。n \leq 5 \times 10^4

先考虑如何写 checker。可以发现这是一个 2-SAT。

打表可以发现合法方案的数量至少占常数分之1。然后直接随即可。