有两个集合,给出n组限定关系,每一个元素要放进一个集合里,限制关系(a,b)为一个集合选择a就不能选择b。输出一种分组方案

不放假设元素a对应的集合中的另一个元素为a'
矛盾关系可以转化为:选择a就必须选择b'
同样,选择b就必须选择a'

这个”必须“关系是可以传递的,所以可以用图论模型来做

对于一个强连通分量中的所有元素,只要一个选了,就必须选择剩下所有的元素

如果存在a使得a和a'在一个强联通分量里,无解