vwin官方网站
  咨询电话:15241024079

vwin德赢论坛

种族并查集总结

种族并查集总结

原理

用于描述对象的属性具有传递性的关系,诸如:食物链、朋友的朋友是朋友,敌人的敌人是朋友这种东西

比如,我们可以开一个补集来存放某个对象的反面(如A的反面A",可以理解为A的反面的招牌,所有是A的反面的元素都与它相连,归为它旗下),如果元素A与元素B的反面B"联通则说明元素A与元素B不联通

当然,对象的属性不一定只有两种(非敌人即朋友),也可以是多种属性(A吃B,B吃C,C吃A),此时开(n)个补集就好了

其实,反向并查集就是种族并查集的一种。

实现

通过多开(m)倍并查集数组f[n*m],并将一个元素(i)的第(j)个属性表示为(i+nimes j),来实现种族并查集总结

比如表示A与B不是朋友:

merge(A, B+n);merge(B, A+n);

即B的敌人是A的朋友,A的敌人是B的朋友

洛谷 P1892 团伙洛谷 P1525 关押罪犯洛谷 P2024 食物链