algorithm - 有多少种方法可以给圆形中未着色的边缘着色

Question

给定圆上的 n 个点并绘制所有边 (C(2,n))。其中一些边缘已经用蓝色或红色着色。您应该了解有多少种方法可以为静止边缘着色，以便获得具有以下条件的最终图片：

1. 所有边缘都是彩色的。
2. 所有三角形都有 0 或 2 条红色边。

这里有些例子：

示例 1

输入：n = 3 和 0 条边已经着色。output = 4 ：因为我们可以将所有边缘着色为蓝色，或者仅将其中一个边缘着色为蓝色，其余边缘着色为红色。

示例 2

输入 n = 4 和 4 条边已经着色

1 2 蓝色

2 3 蓝色

3 4 红色

4 1 红色

output = 1 ：因为为静止边缘着色的唯一方法如下：

1 3 蓝色

2 4 红色

约束：

• 3 <= n <= 100,000
• 时间限制：1秒
• 内存限制：256 MB

实际上我不知道此类问题的理想数据结构，我需要你的帮助以获得一些线索

标签： algorithmdisjoint-sets

Answer 1

这是一个线性时间算法。

首先，观察有效着色的每个循环都包含偶数个红色边缘（我将把它留作练习）。给定生成树的颜色，只存在一个有效补全。唯一性很容易证明，因为不在树中的每条边的颜色由与它形成循环的树边的颜色的奇偶性决定。我将把有效性作为另一个练习（时间紧迫，抱歉）。

该算法是，使用深度优先搜索来查找给定边缘的生成森林，存储每个节点与其树的根之间的边缘颜色的奇偶性。给定这些数据，我们可以验证不在森林中的每条边的给定颜色。如果有任何错误，则有 0 个着色。否则，有 2^（树数减一）着色。