题目理解

我们有 $N$ 个议员，需要将他们分配到 A 或 B 两个政党。给出了连续5天的辩论照片，每张照片记录了当天发生辩论的议员对。

关键约束：每个议员最多和两个不同的同党议员争论。

换句话说，对于每个议员，与其同属一个政党且发生过辩论的议员数量不能超过2个。

关键观察

1. 问题转化

我们可以将问题建模为一个图论问题：

• 节点：议员
• 边：两个议员在某天发生过辩论

约束条件转化为：在同一个政党内，每个节点的度数不超过2。

2. 图的性质分析

由于每个政党内每个节点的度数不超过2，这意味着：

• 在每个政党内部，连通分量只能是：
  • 孤立点
  • 链（路径）
  • 环

不能有度数≥3的节点，否则会违反约束。

3. 五天数据的处理

五天的照片实际上是五天辩论记录的并集。我们需要考虑所有五天中出现的辩论关系。

算法设计

1. 图构建

首先构建一个无向图 $G = (V, E)$：

• $V$: 所有议员（1到$N$）
• $E$: 五天中所有出现过的辩论关系（去重）

2. 约束重新表述

对于图 $G$ 的每个节点 $v$，设：

• $deg_A(v)$: 在政党A中与$v$同党且相邻的节点数
• $deg_B(v)$: 在政党B中与$v$同党且相邻的节点数

约束条件：对于每个节点 $v$，$deg_A(v) \leq 2$ 且 $deg_B(v) \leq 2$

3. 算法思路

由于约束相对宽松（每个政党内度数≤2），我们可以采用贪心或启发式方法：

方法1：基于度数的贪心分配

1. 按节点度数从高到低排序
2. 依次为每个节点选择政党，选择能最小化约束违反的政党
3. 如果两种选择都会违反约束，回溯或调整

方法2：连通分量分解

1. 找出图的所有连通分量
2. 对每个连通分量独立分配政党
3. 对于每个分量，检查是否能满足度数约束

4. 具体实现策略

步骤1：预处理

• 构建邻接表表示图
• 计算每个节点的度数
• 记录每个节点的邻居列表

步骤2：政党分配

使用贪心策略：

• 初始化所有节点为未分配
• 对于每个节点，尝试分配政党A
  • 检查如果分配A，该节点及其已分配邻居是否满足约束
  • 如果违反约束，尝试分配政党B
• 如果两种分配都违反约束，需要调整已分配节点的政党

步骤3：约束检查

对于节点 $v$ 分配政党 $P$ 时，检查：

1. $v$ 在政党 $P$ 中的度数：统计已分配且选择政党 $P$ 的邻居数量
2. 对于 $v$ 的每个已分配邻居 $u$（与 $v$ 同党），检查 $u$ 在政党 $P$ 中的度数是否超过2

复杂度分析

• 图构建：$O(5 \times P)$，其中 $P \leq N/2$，即 $O(N)$
• 贪心分配：每个节点需要检查其邻居，最坏情况 $O(N \times \text{平均度数})$
• 由于每个节点度数不会太高（稀疏图），实际运行效率较好

特殊情况处理

1. 高度数节点

如果某个节点的度数 > 4，那么无论如何分配都会违反约束（因为最多只能在同一个政党中有2个邻居）

但实际上，根据约束，这种情况不会发生，因为：

• 总度数 = A政党度数 + B政党度数 ≤ 4
• 所以每个节点的总度数不会超过4

2. 小连通分量

对于小的连通分量（如孤立点、边、三角形等），可以更容易找到满足约束的分配。

3. 环结构

对于环结构，需要确保环上相邻节点不同政党，或者环的长度足够大以容纳度数约束。

正确性保证

1. 可行性分析

由于约束相对宽松，且题目保证有解，我们的贪心策略在大多数情况下能找到可行解。

2. 回溯机制

如果贪心分配遇到冲突，可以采用有限的回溯：

• 重新分配导致冲突的节点
• 或者重新分配整个连通分量

优化技巧

1. 度数排序

优先处理高度数节点，因为它们的选择空间更小。

2. 连通分量分解

将大图分解为小连通分量，分别求解，降低问题复杂度。

3. 早期剪枝

在分配过程中，如果发现某个节点的两种选择都会违反约束，立即回溯。

总结

这道题的核心在于将政治辩论关系建模为图论问题，并通过巧妙的政党分配满足度数约束：

1. 图论建模：将辩论关系抽象为图的边
2. 约束分析：理解"同党度数≤2"的图论含义
3. 贪心分配：基于度数优先处理约束严格的节点
4. 可行性保证：利用图的稀疏性和约束的相对宽松性

这种"图论建模 + 约束满足"的思路在解决复杂的分配问题时非常有效，特别是当约束可以转化为图的性质时。题目虽然数据规模较大，但由于约束的特殊性，使得贪心方法在实践中有很好的效果。