arc062d | Painting Graphs with AtCoDeer

link

---

好厉害的“套路题”。

首先你会发现直接 Burnside 这个群是描述不清的。

环套着环，错综复杂，不好分析。

那怎么办呢？

其实我当时也想到了，有没有一种可能，能使得这个图能通过旋转得到所有颜色相同的图？

---

这个结论是正确的。（我当时构造不出来了。。。。）

大概的感觉就是，如果有一条边在两个环中（只要不是环，这样的边始终存在），可以通过类似拧魔方的方法，让两条边交换 。

那么能否交换任意两边呢？

事实上也是可以的。两条边一定在一个环里。

我们可以将任意一条边转到一个“三度的可swap的点处”，然后将他swap出环，接下来把另外的边也转到这个点处，swap，最后还原即可。

真的很像魔方。。。。。。

不难发现一定是一个仙人掌块是独立的。也就是点双独立。

剩下的点双要特判一下 o-o 和环（burnside大板子）就好了/cy

---