请帮忙看下这题哪里有错（C++并查集模板题，亲戚）

来源：蜘蛛抓取(WebSpider) 时间：2018-10-02 04:08 标签： 题请

并查集是一种树型的数据结构鼡于处理一些不相交集合的合并问题。
1－合并两个不相交集合
2－判断两个元素是否属于同一个集合

我转载的一个并查集介绍：（很详细）

用一个经典的种类并查集做例子食物链那一题

//num数组 0表示和父节点同类 1表示被父节点吃，2表示吃父节点 //所有取模前提条件都是A吃B B吃C C吃A 长度为3的环 //要先保存这个父节点否則下面压缩路径后p[x]会变 //q是操作 1表示同类 2表示a吃b //q如果是1 那么a和b就是同类，num值不同即为假话 //q如果是2 那么a吃b那么为了使得满足三角关系，b必须吃父节点也就是num[b]为2,num[a]为1,或者num[b]为0,num[a]为2,即a吃b，a吃fa/fbb和父节点同类,所以加了个取模 //这里q-1是因为我们定义0同类 1被吃 比题目输入少1 //这个公式可以通过向量的关系图推出（见上图） //没有关系连通，所以肯定不会矛盾

我要回帖

更多关于 题请 的文章

 

随机推荐