#3732. 弦图最小染色与完美消除序
弦图最小染色与完美消除序
题目描述
题目背景
给定一张无向简单图 ,其中 ,。
称一个顶点序列 是一个完美消除序(Perfect Elimination Ordering,PEO),当且仅当对每个 ,顶点 在子图 中的邻接点集合构成一个团(即这些邻接点两两相邻)。
称图 是弦图,当且仅当 存在至少一个完美消除序。
本题要求你判断给定的图是否为弦图;若是,进一步求出该图的色数 (即最少需要的颜色数,使得任意相邻两顶点颜色不同)。
题目任务
- 判断图 是否为弦图。
- 若 是弦图,输出其色数 ;否则输出
-1。
说明
- 图不保证连通。
- 图中无重边、无自环。
- 色数定义为对图进行正常顶点染色所需的最少颜色数。
输入格式
第一行两个整数 ,表示顶点数与边数。
接下来 行,每行两个整数 (,),表示一条无向边。保证没有重边与自环。
输出格式
输出一行一个整数:
- 若 是弦图,输出 ;
- 否则输出
-1。
样例
4 4
1 2
2 3
3 4
4 1
-1
5 6
1 2
2 3
3 1
3 4
4 5
5 3
3
说明/提示
数据范围
- 保证
部分分
- 对于 的数据,。
- 对于 的数据,。
- 对于另 的数据,保证图连通且为树。
- 对于 的数据,,。
提示
- 弦图的一个经典性质:对弦图做**最大势算法(MCS)**得到的顶点序是完美消除序。
- 弦图的色数等于其最大团的大小。
- 注意图可能不连通,需要对每个连通分量分别处理。
解析
解题思路
本题要求判断无向图是否为弦图,并在是弦图时求色数。核心利用弦图的两个经典性质:
- 最大势算法(MCS):从所有顶点势为 0 开始,每次取出当前势最大的未删顶点加入序列,并给其未删邻居势加 1。对弦图而言,MCS 产生的序列的逆序是完美消除序(PEO)。
- 弦图色数 = 最大团大小。在 PEO 中,每个顶点与其后面所有邻居构成一个团,因此最大团大小等于所有顶点“后面邻居数 + 1”的最大值。
算法流程
- 读入图,用邻接表存储。
- 运行 MCS:用优先队列维护(势,顶点),懒惰删除已用顶点和过期势。得到 MCS 序后反转作为候选 PEO。
- 验证 PEO:对 PEO 中每个顶点 ,找出其后面所有邻居。取其中在 PEO 中位置最靠前(即 rank 最小)的顶点 ,检查其余后面邻居是否都与 相邻。若存在不相邻,则不是弦图,输出
-1。 - 同时统计最大团大小:每个顶点的后面邻居数 + 1 即为一个团的大小,取最大值。
- 若是弦图,输出最大团大小(即色数)。
复杂度分析
- MCS 使用优先队列:每个顶点每次势增加入队一次,总入队 次,每次 ,故 。
- 验证 PEO:对每个顶点遍历其邻接表,总 ;邻接集合查询平均 。
- 空间:邻接表 ,邻接集合 。
对于 、,总复杂度约 ,在 1 秒内可轻松通过。
注意事项
- 图可能不连通,但 MCS 和 PEO 验证对非连通图同样适用(各连通分量独立处理,算法自然覆盖)。
- 验证 PEO 时,必须检查“后面邻居集合构成团”。选取 rank 最小的后面邻居 作为枢纽,检查其余邻居是否都与 相邻即可,这是 PEO 判定的标准方法。
- 最大团大小在验证过程中顺带统计,无需额外搜索。
来源
AI 生成 · 云端大模型(域):deepseek-chat · NOI/NOI+/CTS · 图论