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

理解思想

一.团伙

给定若干满足如下两条的关系，求会构成多少个团伙：

、

为朋友。

、

为敌人。

普通并查集维护朋友关系依靠的是朋友关系具有传递性，即朋友的朋友还是朋友。但是，敌人的敌人是朋友并不满足上述传递性，因此需要想办法将问题转化为满足传递性。这就是扩展域并查集维护的问题方法。

每个人存在两种关系，将两种关系分为两个集合：

朋友集(

)。

敌人集(

)。

对于每种关系：

如果

、

是朋友，就将

加入

的朋友集，即操作：

//将y加入x的朋友集(x)

add(x,y);

如果

、

是敌人，就将

加入

的敌人集，将

加入

的敌人集，即操作：

//分别将x,y加入对方的敌人集

add(x+n,y);//x的敌人集(x+n)

add(y+n,x);//y的敌人集(y+n)

这样实际上利用了：

敌人的敌人就是朋友这一性质，将无法维护（无法合并）的敌对关系

与

，换成了敌人与敌人间的朋友关系

与

。

二.食物链

给定若干满足如下三条的关系，求有多少条件不合法：

、

为同类。

吃

。

若

吃

，

吃

，则有

吃

。

每个人存在三种关系，将三种关系分为三个集合：

同类集(

)。

可吃集(

)。

被吃的集(

)，后面简称为被吃集。

注意：拥有多种关系时，要进行关系传递。如

与

同类，

能吃的

也能吃。

对于两种情况：

如果

、

是同类，就将

加入

的同类集，将

能吃的加入

的可吃集，将吃

的加入

的被吃集，即操作：

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)

如果

吃

，就将

加入

的可吃集，将

加入

的被吃集，将

加入

的被吃集(根据关系

，

吃

，

吃

)，即操作：

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)