最大独立集

【题目描述】

给定一张有 $N$ 个顶点、$M$ 条边的简单无向图。第 $i$ 条边为 $(u_i, v_i)$。

求最大独立集。

【输入】

$N$ $M$
$u_0$ $v_0$
$u_1$ $v_1$
$\vdots$
$u_{M - 1}$ $v_{M - 1}$

【输出】

$X$
$p_0$ $p_1$ ... $p_{X - 1}$

$X$ 为最大独立集的大小，$p_i$ 为顶点编号。

【输入样例】

8 10
0 1
2 3
4 5
6 7
0 2
2 4
4 6
1 3
3 5
5 7

【输出样例】

4
5 2 1 6

【输入样例2】

7 9
0 1
1 2
2 0
2 3
3 4
4 2
4 5
5 6
6 4

【输出样例2】

3
6 1 3

【数据范围】

• $1 \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)$

【来源】

Library Checker（yosupo06） maximum_independent_set

本题为 special judge（输出任意合法解），暂不可本地评测。