扩展域并查集理解性总结
纯文字内容，较短，较枯燥，但感谢你能点进来并完成阅读。前置：并查集
扩展域并查集(种类并查集)
理解思想
一.团伙
[*]给定若干满足如下两条的关系，求会构成多少个团伙：
[*]\(x\)、\(y\) 为朋友
[*]\(x\)、\(y\) 为敌人
[*]普通并查集维护朋友关系依靠的是朋友关系具有传递性，即朋友的朋友还是朋友。但是，敌人的敌人是朋友并不满足上述传递性，因此需要想办法将问题转化为满足传递性。这就是扩展域并查集维护的问题方法。
[*]每个人存在两种关系，将两种关系分为两个集合：
[*]朋友集(\(x\))
[*]敌人集(\(x+n\))
[*]对于每种关系：
[*]如果 \(x\)、\(y\) 是朋友，就将 \(y\) 加入 \(x\) 的朋友集，即操作：//将y加入x的朋友集(x)
add(x,y);
[*]如果 \(x\)、\(y\) 是敌人，就将 \(y\) 加入 \(x\) 的敌人集，将 \(x\) 加入 \(y\) 的敌人集，即操作：//分别将x,y加入对方的敌人集
add(x+n,y);//x的敌人集(x+n)
add(y+n,x);//y的敌人集(y+n)
[*]这样实际上利用了：
敌人的敌人就是朋友这一性质，将无法维护（无法合并）的敌对关系 \(x\) 与 \(y\) ，换成了敌人与敌人间的朋友关系 \(x+n\) 与 \(y\)。
二.食物链
[*]给定若干满足如下三条的关系，求有多少条件不合法：
[*]\(x\)、\(y\) 为同类
[*]\(x\) 吃 \(y\)
[*]若 \(x\) 吃 \(y\)，\(y\) 吃 \(z\)，则有 \(z\) 吃 \(x\)
[*]每个人存在三种关系，将三种关系分为三个集合：
[*]同类集(\(x\))
[*]可吃集(\(x+n\))
[*]\(x\) 被吃的集(\(x+2n\))，后面简称为被吃集
[*]注意：拥有多种关系时，要进行关系传递。如 \(x\) 与 \(y\) 同类，\(y\) 能吃的 \(x\) 也能吃。
[*]对于两种情况：
[*]如果 \(x\)、\(y\) 是同类，就将 \(y\) 加入 \(x\) 的同类集，将 \(y\) 能吃的加入 \(x\) 的可吃集，将吃 \(y\) 的加入 \(x\) 的被吃集，即操作：add(x,y);//将y加入x的同类集(x)
add(x+n,y+n);//将y可吃的加入x的可吃集(x+n)
add(x+2*n,y+2*n);//将吃y的加入x的被吃集(x+2n)
[*]如果 \(x\) 吃 \(y\)，就将 \(y\) 加入 \(x\) 的可吃集，将 \(x\) 加入 \(y\) 的被吃集，将 \(y+n\) 加入 \(x\) 的被吃集(根据关系 \(3\)，\(y\) 吃 \(z\)，\(z\) 吃 \(x\))，即操作：add(x+n,y);//将y加入x的可吃集(x+n)
add(y+2*n,x);//将x加入y的被吃集(y+2n)
add(x+2*n,y+n);//将y+n加入x的被吃集(x+2n)
总结
[*]分析每种个体存在多少种不同的关系，将这些关系分为不同的集合，最后通过并查集维护。
欢迎指出疏漏。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 感谢分享 懂技术并乐意极积无私分享的人越来越少。珍惜 懂技术并乐意极积无私分享的人越来越少。珍惜 热心回复！ 新版吗？好像是停更了吧。 分享、互助 让互联网精神温暖你我
页:
[1]