并查集的基础知识

最近有学到一种更加通用的方法,因为它还适用于1182食物链中有三种集合相关联的情况,而且此法更为简洁。

只需加一个rank数组,表示两种派别,值为0和1,初始化为0.
查询时如果两人属于同一集合并且属于派别相同就输出In the same gang.否则输出In different gangs.不属于同一集合则不能判断。
当我们要合并两个集合时,根据当前2人的派别可推出它们的祖先的派别应该怎样改变,见下图:


若此时告诉5号和10号属于不同派别,则6的rank值应修改为1,即rank[6]=(rank[5]+rank[10]+1)%2;
如果告诉4号和10号属于不同派别,则6的rank值应修改为0,即rank[6]=(rank[4]+rank[10]+1)%2;
 
因为在合并时并没有把子树里的每个子节点都修改完,也没有那个必要,所以在find_set时要进行修改,很简单,儿子的值要与父亲的值不同。
原文地址:https://www.cnblogs.com/XBWer/p/2630034.html