Chordal Graph Recognition

AC一覧

Problem Statement
問題文

You are given a simple undirected unweighted graph, consisting of $N$ vertices and $M$ edges.
The $i$-th edge is between vertex $a_i$ and vertex $b_i$.

A graph is chordal if it does not have an induced cycle of length four or more. A perfect elimination ordering is an ordering of the vertices such that for every vertex $v$, $v$ and the neighbors of $v$ that appear after it in the ordering form a clique. It can be shown that a graph is chordal if and only if it has a perfect elimination ordering.

If the graph is chordal, find a perfect elimination ordering. If there are multiple perfect elimination orderings, print any of them.

If the graph is not chordal, find an induced cycle of length four or more. If there are multiple such cycles, print any of them.

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。$i$ 番目の辺は頂点 $a_i$, $b_i$ をつないでいます。

グラフは、長さ $4$ 以上の induced cycle を持たない時、またその時のみ chordal graph と呼びます。 perfect elimination orderingとは、次の条件を満たす頂点の順序付けです: 各頂点 $v$ について、$v$ と $v$ に隣接した、$v$ より後ろの順序の頂点はクリークをなす。

グラフはPerfect elimination orderingを持つときのみ chordal graph であることが知られています。

入力のグラフが chordal graph ならば、perfect elimination ordering を出力してください。 chordal graph ではない場合、長さ $4$ 以上の induced cycle を出力してください。

どちらも複数存在する場合、どれか一つを出力してください。

Constraints
制約

Input
入力

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

Output
出力

If the graph is not chordal, output an induced cycle of length four or more in the following format.

もしグラフが chordal graph ではない場合、次の形式に従い(長さ $4$ 以上の) induced cycle を出力してください。

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

$K$ represents length of the induced cycle. $c_i$ is the $i$-th vertex in the cycle.

$K$ はサイクルの長さ。 $c_i$ はサイクルの $i$ 番目の頂点です。

If the graph is chordal, output a perfect elimination ordering in the following format.

もしグラフが chordal graph の場合、次の形式に従い perfect elimination ordering を出力してください。

YES
$v_0$ $v_1$ $\ldots$ $v_N$

$v_i$ is the $i$-th vertex in the perfect elimination ordering.

$v_i$ は perfect elimination ordering の $i$ 番目の頂点です。

Sample
サンプル

# 1

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
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
NO
5
6 3 2 9 5

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions