查找满足多个互斥条件的分组方法

Question

问题：有n个元素a、b、c、d、e、f...,要求将这些元素拆分成m个分组，同时满足条件：集合{a,b,c,d},{b,d,f},{c,e}....内的元素不能在同一个分组。

默认n和m满足分组条件，1个元素可以出现在多个条件集合内；结果不唯一，只要给出1个较优结果，即各个分组内元素数量较均匀。

我的能想到的方法是，先整理出每个元素与其他元素的互斥关系，比如a不能与{b,c,d}在同1分组，b不能与{a,c,d,f}在同1分组...,然后将每个元素互斥条件最多的，从多到少随机分配在m个分组内，每次随机验证是否满足条件，全部随机完成返回结果。

但是这个方法比较暴力，而且不能给出最优解，计算开销也比较大。

求算法大神给个思路或意见。

Answer 1

如果是计算最小要分成几组，可以使用拓扑排序，这里分成指定的组数，需要改进下。建议去看看NOIP2013普及复试中的第4题车站分级的问题，或许那里的解题思想可以借用。