給定數量的集合，找到一組不包含任何給定的數字

Question

給定具有數字的集合數量（0-20例如），我們被要求從0-20中找到最大數字集合不包括任何給定的套（它可以包括從一組數字，而不是整個組） 例如：設定最大數量8和給定的集

{1,2} 
{2,3} 
{7} 
{3,4} 
{5,6,4}, 

一個最大值的解決方案是設置{1，3，5，6，8}。 我正在考慮將它表示爲一個圖形，然後將其引入最大獨立集問題，但是這似乎只在集合僅由成對組成時才起作用，這不成立。任何想法？提前致謝。

Answer 1

爲每組使用位圖，設置適當的位。如果成員少於32個，則可以使用uint32_t。然後可以通過用特定位圖掩蔽所有成員（即，所有集合的聯合），然後使用具有特定位圖的異或來計算全集合包含。如果是子集，結果將全部爲0，否則結果將成爲最大獨立集的成員。