8225: [yosupo] Graph - Chordal Graph Recognition
[Creator : ]
Description
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.
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.
Input
$N$ $M$
$a_0$ $b_0$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{M - 1}$ $b_{M - 1}$
$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.
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.
If the graph is chordal, output a perfect elimination ordering in the following format.
YES
$v_0$ $v_1$ $\ldots$ $v_N$
$v_i$ is the $i$-th vertex in the perfect elimination ordering.
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.
If the graph is chordal, output a perfect elimination ordering in the following format.
YES
$v_0$ $v_1$ $\ldots$ $v_N$
$v_i$ is the $i$-th vertex in the perfect elimination ordering.
Constraints
$1 \leq N \leq 200,000$
$0 \leq M \leq 200,000$
$0 \leq a_i \lt N$
$0 \leq b_i \lt N$
$a_i \neq b_i$
$\lbrace a_i, b_i \rbrace \neq \lbrace a_j, b_j \rbrace (i \neq j)$
$0 \leq M \leq 200,000$
$0 \leq a_i \lt N$
$0 \leq b_i \lt N$
$a_i \neq b_i$
$\lbrace a_i, b_i \rbrace \neq \lbrace a_j, b_j \rbrace (i \neq j)$
Sample 1 Input
4 4
1 3
0 3
1 2
0 1
Sample 1 Output
YES
2 0 1 3
Sample 2 Input
5 4
0 2
1 3
0 1
3 2
Sample 2 Output
NO
4
1 3 2 0
Sample 3 Input
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
Sample 3 Output
NO
5
6 3 2 9 5