最大独立集（Maximum Independent Set）

问题描述

给定一个简单无向图，含 $N$ 个顶点和 $M$ 条边。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。
求该图的一个最大独立集（Maximum Independent Set, MIS）——即顶点子集 $S$，使得 $S$ 中任意两点不相邻，且 $|S|$ 最大。

约束条件

• $1 \leq N \leq 40$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $0 \leq u_i, v_i < N$
• $u_i \ne v_i$
• $(u_i, v_i) \ne (u_j, v_j)$（无重边）

输入

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

输出

$X$
$p_0\ p_1\ \cdots\ p_{X-1}$

$X$ 是最大独立集的大小，$p_i$ 是独立集中第 $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

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

3
6 1 3