URAL 1128 - Partition into Groups

由於想不到, 所以看 solution

做法很簡單, 先隨便 partition
然後 while child x has ≥ 2 enemies in his group, move child x to another group

Let badness = | { (x, y): x, y are enemies and lies in same group } |
可見 badness 在一次 operation 後會下降至少 1
而 initial badness ≤ 3N, 及 0 ≤ badness
所以一定有 solution, 而且 O(N) 找到