有两个集合,给出n组限定关系,每一个元素要放进一个集合里,限制关系(a,b)为一个集合选择a就不能选择b。输出一种分组方案
不放假设元素a对应的集合中的另一个元素为a'
矛盾关系可以转化为:选择a就必须选择b'
同样,选择b就必须选择a'
这个”必须“关系是可以传递的,所以可以用图论模型来做
对于一个强连通分量中的所有元素,只要一个选了,就必须选择剩下所有的元素
如果存在a使得a和a'在一个强联通分量里,无解
有两个集合,给出n组限定关系,每一个元素要放进一个集合里,限制关系(a,b)为一个集合选择a就不能选择b。输出一种分组方案
不放假设元素a对应的集合中的另一个元素为a'
矛盾关系可以转化为:选择a就必须选择b'
同样,选择b就必须选择a'
这个”必须“关系是可以传递的,所以可以用图论模型来做
对于一个强连通分量中的所有元素,只要一个选了,就必须选择剩下所有的元素
如果存在a使得a和a'在一个强联通分量里,无解