给定一个圆上的n个点和所有边(C(2,n))被画出来有些边缘已经被涂成蓝色或红色。您应该了解有多少种方法可以为静止边缘上色,以便在以下条件下获得最终图片:
所有边都是彩色的。
所有三角形都有0或2条红色边。
下面是一些例子:
例1
输入:n=3,0个边已经着色。
输出=4:因为我们可以将所有边涂成蓝色,或者只有一条边涂成蓝色,其余边涂成红色。
例2
输入n=4和4已着色的边数
12蓝色
23蓝色
34红色
41红色
output=1:因为对休息边上色的唯一方法如下:
13蓝色
2 4红色
限制条件:
3时限:1秒
内存限制:256 MB
实际上我不知道这个问题的理想数据结构,我需要你的帮助

最佳答案

这是一个线性时间算法。
首先,观察有效着色的每个循环都包含偶数条红色边(我将把这个作为练习)。给定生成树的颜色,就存在一个有效的完成。唯一性很容易证明,因为每一条不在树中的边的颜色是由它形成一个循环的树的边的颜色的奇偶性决定的。我将把有效期留作另一个练习(抱歉,时间紧迫)。
该算法是利用深度优先搜索来寻找给定边缘的生成林,存储每个节点与其树根之间的边缘颜色奇偶性给定这些数据,我们可以验证森林中每个边缘的给定颜色。如果有错误,则有0种颜色否则,有2^(树数减1)种颜色。

10-06 00:28