扩展域并查集理解性总结

纯文字内容，较短，较枯燥，但感谢你能点进来并完成阅读。

前置：并查集

扩展域并查集(种类并查集)

理解思想

一.团伙

• 给定若干满足如下两条的关系，求会构成多少个团伙：
  • (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) 

总结

• 分析每种个体存在多少种不同的关系，将这些关系分为不同的集合，最后通过并查集维护。

欢迎指出疏漏。