PKU 1466 Boys and Girls

想不到這道是若干年後被改難然後翻炒…

題意說給出N人，每人會對某幾個人有關係，問最多可以選多少人，使得這群人互相不會有關係。

如果把沒有關係的人連一條邊，題目正好就是求Maximum Clique。不過這道題給的不是這條邊，而是赤裸裸的告訴你這是二分圖。明顯地求Maximum Independent Set。輕輕用簡單的二分圖匹配就搞定了。

至於難版的那個，只是沒有這般赤裸裸而已…