在最大度为 D 的简单无向图上为每条边分配颜色，使任意相邻边颜色不同；一般可在 (D+1) 色内构造，二分图可达 D 色。
Description: Given a simple, undirected graph with max degree , computes a -coloring of the edges such that no neighboring edges share a color. Time: O(NM)
-
定义与背景
- 边染色：将无向图 G=(V,E) 的每条边 e 赋予一个颜色 c(e)，满足共享端点的两边颜色不同。
- 色数目标：设最大度为 Δ(G)=D，一般图存在使用 D+1 种颜色的多项式构造；对二分图可在 D 种颜色内完成。
- 相关结论与工程取舍：最优 D-着色在一般图中是困难问题；因此常用 (D+1)-色构造作为稳定上界。
-
典型适用场景
- 调度/资源分配：如“端口/信道冲突避免”的时隙/频段分配，边表示冲突关系。
- 分解为匹配：将图的边集拆成若干“同色匹配”，便于并行执行或批处理。
-
接口/数据结构（据实现）
- 函数：edgeColoring(int N, vector
eds) → vi colors - N：点数；eds：边列表（按输入顺序需要返回对应颜色）。
- 返回：每条边的颜色编号 0..ncols-1，其中 ncols= D+1（一般图）或 D（二分图特化）。
- 邻接槽：为每个点维护 ncols 个“颜色槽”，表示该点在某颜色是否已被占用。
- 辅助结构：fan、loc、free、cc（度）等，用于寻找/释放可用颜色槽并维持一致性。
- 函数：edgeColoring(int N, vector
-
核心流程/要点（Misra–Gries 风格的 (D+1) 色构造）
- 统计每点度 cc[u]，令 ncols = max(cc)+1（一般图安全上界）。
- 初始化每个点的 ncols 槽，标记已占/空闲；构建边序遍历。
- 处理每条边 (u,v)：
- 若存在某颜色 d 在 u 与 v 处均空闲，则直接赋色 d。
- 否则构造“扇形 fan”在 u 附近旋转，寻找一条可释放的颜色链（交替路），对相邻边沿颜色链翻转，腾出颜色槽后再为 (u,v) 赋色。
- 在实现中以 fan、loc、free 的更新保持局部一致；失败时继续扩展/旋转直至成功。
- 遍历完成后，按 eds 顺序导出每条边的颜色编号。
-
特性与边界条件
- 二分图退化为 D 色：将边集分解为不相交的最大匹配序列，每轮用匹配填满一种颜色，最终色数不超过 D。
- 输入限制：简单无向图（不允许自环/多重边）；若存在重边，应按多重图版本修订（槽与 fan 的语义需扩展）。
- 稳健性：颜色槽与 fan 链的维护需与边序一致，避免出现“同端点同色”冲突。
- 时间复杂度：整体 O(NM) 级别，适用于中等规模。
-
变体/扩展
- 二分图边染色（D 色）：可迭代求最大匹配或按度分层匹配；也可用网络流建模（每色一层）但常数较大。
- 在线/动态边染色：在插入/删除边时维护颜色；(D+1)-色仍成立，但需要动态维护交替链。
- 一般图最优 D-色：为 NP-难问题，竞赛与工程中通常不追求最优，仅用 (D+1)-色的确定性构造。
-
正确性要点与不变式
- 有效性：同色边构成匹配；任一赋色或颜色链翻转均保持每点“每种颜色至多占 1 条边”的约束。
- 终止性：颜色链在有限槽空间内必定找到可释放位置或闭环，从而完成当前边赋色。
- 上界保证：ncols ≥ D+1 时，总能为任一新边找到可行颜色（或通过链翻转释放）。
-
与相邻技术对比与取舍建议
- 与匹配分解：二分图优先使用“匹配分解为 D 组”的方案（简单且最优）；一般图采用 (D+1) 色构造稳定可靠。
- 与流/割：流模型可用于二分图匹配式染色，但对一般图并不直接给出 (D+1)-色构造。
- 与带权匹配 079-图论-带权匹配：边染色关注冲突约束下的分组；带权匹配关注权和最优，与染色目标不同。