题目 30101

弦图判定

查看题解 ↗GitHub ↗如何评测
题号
30101
时间限制
10000 ms
内存限制
1024 MB
标签
图论
来源
Library Checker (yosupo06) - chordal_graph_recognition

【题目描述】

给定一个简单无向无权图,由 NN 个顶点和 MM 条边组成。第 ii 条边连接顶点 aia_i 和顶点 bib_i。

如果一个图不包含长度为四或更长的诱导环,则称其为弦图。 完美消除序列是顶点的一个排列,使得对于每个顶点 vv,vv 以及在该排列中出现在它之后的 vv 的邻居构成一个团。 可以证明,一个图是弦图,当且仅当它存在完美消除序列。

如果图是弦图,请找出一个完美消除序列。如果存在多个完美消除序列,输出任意一个即可。

如果图不是弦图,请找出一个长度为四或更长的诱导环。如果存在多个这样的环,输出任意一个即可。

【输入】

文本
$N$ $M$
$a_0$ $b_0$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{M - 1}$ $b_{M - 1}$

【输出】

如果图不是弦图,请按以下格式输出一个长度为四或更长的诱导环。

文本
NO
$K$
$c_0$ $c_1$ $\ldots$ $c_K$

KK 表示诱导环的长度。

cic_i 是环中的第 ii 个顶点。

如果图是弦图,请按以下格式输出一个完美消除序列。

文本
YES
$v_0$ $v_1$ $\ldots$ $v_N$

viv_i 是完美消除序列中的第 ii 个顶点。

【输入样例】

文本
4 4
1 3
0 3
1 2
0 1

【输出样例】

文本
YES
2 0 1 3

【输入样例2】

文本
5 4
0 2
1 3
0 1
3 2

【输出样例2】

文本
NO
4
1 3 2 0

【输入样例3】

文本
10 15
0 1
1 2
2 3
3 4
4 0
5 6
6 7
7 8
8 9
9 5
0 5
1 7
2 9
3 6
4 8

【输出样例3】

文本
NO
5
6 3 2 9 5

【数据范围】

  • 1≤N≤2000001 \leq N \leq 200000
  • 0≤M≤2000000 \leq M \leq 200000
  • 0≤ai<N0 \leq a_i \lt N
  • 0≤bi<N0 \leq b_i \lt N
  • ai≠bia_i \neq b_i
  • {ai,bi}≠{aj,bj}(i≠j)\lbrace a_i, b_i \rbrace \neq \lbrace a_j, b_j \rbrace (i \neq j)

【来源】

Library Checker(yosupo06) chordal_graph_recognition

本题为 special judge(输出任意合法解),暂不可本地评测。

数据下载

题目 30101 的公开数据

正在读取文件列表…

常用命令

题目 30101 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。