BZOJ4316 小C的独立集 【仙人掌】

图论小王子小C经常虐菜，特别是在图论方面，经常把小D虐得很惨很惨。

这不，小C让小D去求一个无向图的最大独立集，通俗地讲就是：在无向图中选出若干个点，这些点互相没有边连接，并使取出的点尽量多。

小D虽然图论很弱，但是也知道无向图最大独立集是npc，但是小C很仁慈的给了一个很有特点的图： 图中任何一条边属于且仅属于一个简单环，图中没有重边和自环。小C说这样就会比较水了。

小D觉得这个题目很有趣，就交给你了，相信你一定可以解出来的。

第一行，两个数n， m，表示图的点数和边数。

第二~m+1行，每行两个数x，y，表示x与y之间有一条无向边。

输出这个图的最大独立集。

5 6

1 2

2 3

3 1

3 4

4 5

3 5

2

100% n <=50000, m<=60000

假设这是一棵树，设\(f[i][0]\)表示\(i\)节点为根，不选\(i\)的最大数量，\(f[i][1]\)表示选择\(i\)的最大数量

转移就很简单了，不选\(i\)，儿子可以选可以不选，选了\(i\)，儿子必须选

如果是仙人掌的话，就先忽略环上的点，然后单独考虑环的影响传递到最高点