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\)，兒子必須選

如果是仙人掌的話，就先忽略環上的點，然後單獨考慮環的影響傳遞到最高點