8219: [yosupo] Graph - Maximum Independent Set
[Creator : ]
Description
Given a simple undirected graph with $N$ vertices and $M$ edges. $i$-th edge is $(u_i, v_i)$。
Calculate the maximum independent set.
Calculate the maximum independent set.
Input
$N$ $M$
$u_0$ $v_0$
$u_1$ $v_1$
:
$u_{M - 1}$ $v_{M - 1}$
$u_0$ $v_0$
$u_1$ $v_1$
:
$u_{M - 1}$ $v_{M - 1}$
Output
$X$
$p_0$ $p_1$ ... $p_{X - 1}$
$X$ is the size of MIS, and $p_i$ is the vertex index.
$p_0$ $p_1$ ... $p_{X - 1}$
$X$ is the size of MIS, and $p_i$ is the vertex index.
Constraints
$@{param.N_MIN} \leq N \leq 40$
$0 \leq M \leq \frac{N(N-1)}{2}$
$0 \leq u_i, v_i < N$
$u_i \neq v_i$
$(u_i, v_i) \neq (u_j, v_j)$
$0 \leq M \leq \frac{N(N-1)}{2}$
$0 \leq u_i, v_i < N$
$u_i \neq v_i$
$(u_i, v_i) \neq (u_j, v_j)$
Sample 1 Input
8 10
0 1
2 3
4 5
6 7
0 2
2 4
4 6
1 3
3 5
5 7
Sample 1 Output
4
5 2 1 6
Sample 2 Input
7 9
0 1
1 2
2 0
2 3
3 4
4 2
4 5
5 6
6 4
Sample 2 Output
3
6 1 3