题解：图边着色问题的欧拉回路构造法

---

问题分析

本题要求给无向图的边染红色(1)或绿色(2)，使得每个度数≥2的顶点都同时连接两种颜色的边。需要判断是否有解，并构造方案。

关键约束：

• 对每个顶点 $v$，如果 $\deg(v) \ge 2$，那么它必须同时有红边和绿边
• 如果 $\deg(v) = 1$，该顶点可以只有一种颜色的边
• 如果 $\deg(v) = 0$，不考虑

---

核心观察

1. 度数奇偶性的重要性

考虑每个度数≥2的顶点：

• 如果它只连接一种颜色的边，那么另一种颜色的边数为0
• 要避免这种情况，需要精心安排边的颜色

2. 转化为欧拉回路问题

关键思路：将边着色问题转化为寻找图的欧拉回路，并在回路上交替着色。

为什么有效？

• 在欧拉回路上交替着色（红绿红绿...）
• 对于回路上的每个顶点（除了起点），进入边和离开边颜色不同
• 因此每个内部顶点都有两种颜色的边

3. 处理度数为奇数的顶点

欧拉回路要求所有顶点度数为偶数。如果存在奇度顶点，需要添加虚拟边将它们配对，使所有顶点度数变为偶数。

---

算法框架

第一步：连通分量处理

图可能不连通，需要分别处理每个连通分量：

• 使用BFS找到连通分量
• 对每个分量独立处理

第二步：奇度顶点处理

对于每个连通分量：

1. 统计奇度顶点数量
2. 如果奇度顶点数为奇数且边数为奇数且没有奇度顶点（特殊情况），无解
3. 将奇度顶点两两配对，添加虚拟边（不在最终答案中输出）

第三步：寻找欧拉回路/欧拉迹

使用Hierholzer算法寻找欧拉回路：

• 如果有奇度顶点，从某个奇度顶点开始找欧拉迹
• 如果没有奇度顶点，找一个环（选择度数>2的顶点开始以确保回路经过它）
• 使用当前弧优化防止超时

第四步：交替着色

在找到的欧拉回路/迹上：

• 给第一条边着色1（红）
• 后续边交替着色2,1,2,1...
• 记录每条边的颜色

第五步：输出结果

按输入顺序输出每条边的颜色。

---

关键实现细节

虚拟边的处理

for (int j = 3 ; j + 1 <= len ; j += 2)
    AddEdge(odd[j], odd[j + 1]),
    AddEdge(odd[j + 1], odd[j]);

将奇度顶点两两配对添加虚拟边，不记录这些边的颜色。

Hierholzer算法

void DFS(const int &u) {
    for (int &i = cur[u] ; i ; i = Graph[i].nxt)
        if (! edgVis[i >> 1]) {
            int id = i >> 1;
            edgVis[i >> 1] = true;
            DFS(Graph[i].to);
            tour[++ tot] = id;  // 后序记录边
        }
}

使用cur[u]当前弧优化，避免重复检查已访问边。

特殊情况判断

if (edgCnt == t && edgCnt % 2 && ! len)
    return puts("0"), 0;

当连通分量是奇环（顶点数=边数且为奇数）且没有奇度顶点时，无解。因为在奇环上交替着色会导致起点只有一种颜色的边。

起始点选择

• 有奇度顶点：从第一个奇度顶点开始
• 无奇度顶点：选择度数>2的顶点（如果存在），否则任选

---

正确性证明

1. 着色满足条件

对于欧拉回路上的任意顶点 $v$（除了起点终点可能重合）：

• 如果 $\deg(v) \ge 2$，它在回路上至少有一条进入边和一条离开边
• 由于交替着色，进入边和离开边颜色不同
• 因此 $v$ 同时连接两种颜色的边

起点终点重合的情况（回路）同样满足。

2. 奇度顶点配对的有效性

添加虚拟边将奇度顶点变为偶度，确保欧拉回路存在。虚拟边不参与最终着色，不影响结果。

3. 特殊情况处理

奇环情况：考虑三角形（3个顶点，3条边）。交替着色会导致每个顶点连接的两条边颜色相同，违反条件。因此无解。

---

复杂度分析

• 时间复杂度：$O(N + M)$
  • BFS：$O(N + M)$
  • Hierholzer算法：$O(M)$，使用当前弧优化
  • 奇度顶点配对：$O(N)$
• 空间复杂度：$O(N + M)$

对于 $N, M \le 10^5$ 完全可行。

---

算法优势

1. 利用欧拉回路性质：自然实现颜色交替
2. 处理非连通图：分别处理每个连通分量
3. 处理奇度顶点：通过添加虚拟边保证欧拉回路存在
4. 高效实现：使用当前弧优化避免重复访问

---

总结

本题是一道图着色与欧拉回路的综合题目，主要考察：

1. 问题转化能力：将着色问题转化为欧拉回路问题
2. 欧拉回路算法：Hierholzer算法的应用与优化
3. 奇度顶点处理：通过添加虚拟边保证回路存在
4. 特殊情况分析：识别并处理无解情况（如奇环）

算法的核心在于认识到：在欧拉回路上交替着色可以保证每个内部顶点连接两种颜色的边。通过添加虚拟边处理奇度顶点，使得该策略适用于一般图。

这种"欧拉回路+交替着色"的方法是解决类似边着色约束问题的经典范式，展示了如何将组合构造问题转化为图论算法问题。