带权并查集

上次计科院赛D题，种类并查集做的自闭，看了几天，终于搞懂了~~~~

真开心，好像会了

并查集就不多说了嘛，基本的谁都会

 

 

建立并查集的 father数组（存放当前节点所在集合代表元素编号） 和 dist数组（存放当前节点到所在集合表表元素的关系） 时，需要用编号对所有字符串唯一标记，方便与 father 数组 和 dist 数组中的各元素唯一对应。此时用string类型的数组存储便可以完成，用某个字符串在string数组中存放的位置来表示该字符串即可，这么做有一个缺点，在判断两个字符串的关系的时候需要遍历整个数组找到两个字符串并确定两个字符串的关系，这时候进一步思考可以发现存储映射关系是 map 的强项，用 map 存储就可以更有效的完成查找字符串的编号这个需求

先插入带权并查集基本知识：

带权并查集，是在普通并查集的基础上，给每个元素赋予了特定的权值，该权值表现了当前元素到代表元素（根节点）的某种特定关系，例如亲缘关系等，并且这种关系是有向的。在合并的过程中，相应的也要改变当前元素到代表元素的关系，由于关系是有向的，因此运算应该遵守矢量运算法则。在这个过程中，每个元素到其根节点的关系用 dist［］数组来表示，

如下：

当前已知 a 的根节点是 ra，a 到 ra 的关系是 dist［a］，b 的根节点是 rb ，b 到 rb 的关系是 dist［ b］，且 b 到 a 的关系是 x ，这时候，合并 ra 和 rb 的过程中，dist 数组处理为 ：

dist［ rb ］＝ x ＋dist［a］－dist［b］；

实现如下：

对于字符串关系的存储和维护，在本题中，我将正关系定义为 0 ，反关系定义为 1 。运用上述思想，用 dist 数组中存储的数据表示当前节点到所在集合代表元素的关系。题目中特殊要求在进行字典建立的过程中，每输入一对关系，判断给定的关系之前是否已经建立，未建立或者已建立且所给关系吻合输出YES ，已建立但与所给的关系不吻合输出 NO ，因此在合并的实现中需要对这个需求进行处理。

在两字符串的关系判断环节，同一集合中的两个元素满足如下关系：

已知 A 为集合的代表元素，要求 B 与 C 的关系，由矢量法则可知 

dist［BC］＝ dist［BA］－dist［CA］。

 

特此鸣谢大佬的博客

https://www.cnblogs.com/detrol/p/7533603.html