并查集扩展域:
一般的并查集,元素x与元y之间只存在两种关系:
1:x与y同属一个集合
2:x与y分别属于两个集合
朋友的朋友是我的朋友
而这道题元素x,y之间存在三种关系:
1:x的同类是y
2:x的猎物是y
3:x的天敌是y
所以当告诉我们x,y两个元素之间的关系,我们可以推断三种关系
一:如果x的同类是y说明:
1:x的同类是y的同类,y的同类是x的同类
2:x的猎物是y的猎物,y的猎物是x的猎物
3:x的天敌是y的天敌,y的天敌是x的天敌
二:如果x的猎物是y说明:
1:x的同类是y的天敌,y的同类是x的猎物
2:x的猎物是y的同类,y的猎物是x的天敌
3:x的天敌是y的猎物,y的天敌是x的同类
我们要每个元素x拆分成3种:同类,猎物,天敌
划分分为3个域:
元素x所在的a集合表示x的所有同类,元素x+n所在的b集合表示x的所有猎物,元素x+2n所在的c集合表示x的所有天敌
由于元素扩展至原来3倍,数组空间也扩展int fa[N]
为int fa[3*N]
再判断为真过后,进行以下操作
x的同类是y:
unionset(find(x),find(y)); //关系1
unionset(find(x+n),find(y+n)); //关系2
unionset(find(x+2*n),find(y+2*n)); //关系3
x的猎物是y:
unionset(find(x),find(y)); //关系1
unionset(find(x+n),find(y)); //关系2
unionset(find(x+2*n),find(y+n)); //关系3
。。。鸽一下,过几天再来补