#3732. 弦图最小染色与完美消除序

弦图最小染色与完美消除序

题目描述

题目背景

给定一张无向简单图 G=(V,E)G=(V,E),其中 ∣V∣=n|V|=n,∣E∣=m|E|=m。

称一个顶点序列 v1,v2,…,vnv_1,v_2,\dots,v_n 是一个完美消除序(Perfect Elimination Ordering,PEO),当且仅当对每个 ii,顶点 viv_i 在子图 G[{vi,vi+1,…,vn}]G[\{v_i,v_{i+1},\dots,v_n\}] 中的邻接点集合构成一个团(即这些邻接点两两相邻)。

称图 GG 是弦图,当且仅当 GG 存在至少一个完美消除序。

本题要求你判断给定的图是否为弦图;若是,进一步求出该图的色数 χ(G)\chi(G)(即最少需要的颜色数,使得任意相邻两顶点颜色不同)。

题目任务

  1. 判断图 GG 是否为弦图。
  2. 若 GG 是弦图,输出其色数 χ(G)\chi(G);否则输出 -1。

说明

  • 图不保证连通。
  • 图中无重边、无自环。
  • 色数定义为对图进行正常顶点染色所需的最少颜色数。

输入格式

第一行两个整数 n,mn,m,表示顶点数与边数。

接下来 mm 行,每行两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n,u≠vu\ne v),表示一条无向边。保证没有重边与自环。

输出格式

输出一行一个整数:

  • 若 GG 是弦图,输出 χ(G)\chi(G);
  • 否则输出 -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 

说明/提示

数据范围

  • 1≤n≤20001\le n\le 2000
  • 0≤m≤n(n−1)20\le m\le \frac{n(n-1)}{2}
  • 保证 m≤2×106m\le 2\times 10^6

部分分

  • 对于 20%20\% 的数据,n≤10n\le 10。
  • 对于 40%40\% 的数据,n≤100n\le 100。
  • 对于另 20%20\% 的数据,保证图连通且为树。
  • 对于 100%100\% 的数据,n≤2000n\le 2000,m≤2×106m\le 2\times 10^6。

提示

  • 弦图的一个经典性质:对弦图做**最大势算法(MCS)**得到的顶点序是完美消除序。
  • 弦图的色数等于其最大团的大小。
  • 注意图可能不连通,需要对每个连通分量分别处理。

解析

解题思路

本题要求判断无向图是否为弦图,并在是弦图时求色数。核心利用弦图的两个经典性质:

  1. 最大势算法(MCS):从所有顶点势为 0 开始,每次取出当前势最大的未删顶点加入序列,并给其未删邻居势加 1。对弦图而言,MCS 产生的序列的逆序是完美消除序(PEO)。
  2. 弦图色数 = 最大团大小。在 PEO 中,每个顶点与其后面所有邻居构成一个团,因此最大团大小等于所有顶点“后面邻居数 + 1”的最大值。

算法流程

  1. 读入图,用邻接表存储。
  2. 运行 MCS:用优先队列维护(势,顶点),懒惰删除已用顶点和过期势。得到 MCS 序后反转作为候选 PEO。
  3. 验证 PEO:对 PEO 中每个顶点 viv_i,找出其后面所有邻居。取其中在 PEO 中位置最靠前(即 rank 最小)的顶点 uu,检查其余后面邻居是否都与 uu 相邻。若存在不相邻,则不是弦图,输出 -1。
  4. 同时统计最大团大小:每个顶点的后面邻居数 + 1 即为一个团的大小,取最大值。
  5. 若是弦图,输出最大团大小(即色数)。

复杂度分析

  • MCS 使用优先队列:每个顶点每次势增加入队一次,总入队 O(n+m)O(n+m) 次,每次 O(log⁡n)O(\log n),故 O((n+m)log⁡n)O((n+m)\log n)。
  • 验证 PEO:对每个顶点遍历其邻接表,总 O(n+m)O(n+m);邻接集合查询平均 O(1)O(1)。
  • 空间:邻接表 O(n+m)O(n+m),邻接集合 O(n+m)O(n+m)。

对于 n≤2000n\le 2000、m≤2×106m\le 2\times 10^6,总复杂度约 O((n+m)log⁡n)O((n+m)\log n),在 1 秒内可轻松通过。

注意事项

  • 图可能不连通,但 MCS 和 PEO 验证对非连通图同样适用(各连通分量独立处理,算法自然覆盖)。
  • 验证 PEO 时,必须检查“后面邻居集合构成团”。选取 rank 最小的后面邻居 uu 作为枢纽,检查其余邻居是否都与 uu 相邻即可,这是 PEO 判定的标准方法。
  • 最大团大小在验证过程中顺带统计,无需额外搜索。

来源

AI 生成 · 云端大模型(域):deepseek-chat · NOI/NOI+/CTS · 图论