用c++解决数据结构的划分子集问题

Question

已知集合A={a1,a2,……an}，及集合上的关系R={ (ai,aj) | ai,ajA, ij}，其中(ai,aj)表示ai与aj间存在冲突关系。要求将A划分成互不相交的子集A1,A2,……Ak,(kn)，使任何子集中的元素均无冲突关系，同时要求分子集个数尽可能少。
例 A={1,2,3,4,5,6,7,8,9}
R={ (2,8), (9,4), (2,9), (2,1), (2,5), (6,2),
(5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) }
可行的子集划分为：
A1={ 1,3,4,8 }
A2={ 2,7 }
A3={ 5 }
A4={ 6,9 }
工作过程
初始状态：A中元素放于cq中，result和newr数组清零，组号group=1
第一个元素出队，将r矩阵中第一行“1”拷入newr中对应位置，这样，凡与第一个元素有冲突的元素在newr中对应位置处均为“1”,下一个元素出队
若其在newr中对应位置为“1”，有冲突，重新插入cq队尾，参加下一次分组
若其在newr中对应位置为“0”, 无冲突，可划归本组；再将r矩阵中该元素对应行中的“1”拷入newr中
如此反复，直到9个元素依次出队，由newr中为“0”的单元对应的元素构成第1组,将组号group值“1”写入result对应单元中
令group=2,newr清零，对cq中元素重复上述操作，直到cq中front==rear,即队空

Answer 1

你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答


本次提问扣除的有问必答次数，已经为您补发到账户，我们后续会持续优化，扩大我们的服务范围，为您带来更好地服务。