心血来潮想复习并查集
于是乎今天又刷了一次食物链
当时的合并代码是这样的
void Union()
{
if(ra<rb)
{
p[rb]=ra;
r[rb]=(r[a]-r+d+3)%3;
}
else
{
p[ra]=rb;
r[ra]=(r[a]-r+d+3)%3;
}
}
红色那部分的公式其实我并没有推出来
当时只是觉得应该跟ra<rb情况相似
只要换一下a跟b的位置就可以了
结果WA了三次
最后想起这块不一定对（因为当时本来就是瞎猜的嘛）
所以改了之后又交了一遍果然AC
PS：
其实并查集合并时谁成为谁的父节点都无所谓
上面的判断语句也是多余的= =
以后坚决不这么写了
于是乎今天又刷了一次食物链
当时的合并代码是这样的
void Union()
{
if(ra<rb)
{
p[rb]=ra;
r[rb]=(r[a]-r+d+3)%3;
}
else
{
p[ra]=rb;
r[ra]=(r[a]-r+d+3)%3;
}
}
红色那部分的公式其实我并没有推出来
当时只是觉得应该跟ra<rb情况相似
只要换一下a跟b的位置就可以了
结果WA了三次
最后想起这块不一定对（因为当时本来就是瞎猜的嘛）
所以改了之后又交了一遍果然AC
PS：
其实并查集合并时谁成为谁的父节点都无所谓
上面的判断语句也是多余的= =
以后坚决不这么写了
