问题1：如何判断某个节点是否为该树的根节点？
假设我们用p数组存储x元素的父节点的值 ， 我们可以在最开始将所有的节点存储的值赋为它自己 。这样 ， 若我们在最后还能遇到p[x] == x ， 那么就说明它是树根 。

文章插图
问题2：如何判断某个元素在不在集合里？如果在 ， 如何求该元素的集合编号？
只需要判断该元素在数组中对应的位置的值 ， 一直往上推看看能否找到相应的根节点即可 。伪代码为:：while(p[x] != x) x = p[x] 。
问题3：如何合并两个集合？
只要像上图中的红线那样 ， 让某一个集合成为另一个集合的某个节点（一般我们选择另一个集合的根节点）的子节点就可以 。若p[x] == x ， p[y] == y ， 则令p[x] == y可完成合并 。
但是 ， 在问题2解决方案中 ， 时间复杂度还是较高的 。我们如何优化呢？一旦我们某个节点找到了整棵树的根节点 ， 那么就把它走过的路径上的所有节点都直接指向根节点 。如图：
这样带来的好处是 ， 假若我们后来还要查找一次以前查找过的某个元素在哪个集合 ， 那么就可以一步到位 。如此一来 ， 时间复杂度就接近O（1）了 。
注意 ， 这里p[x]表示的是x的父节点的值而非编号！！因此 ， 该算法要求不同集合中的元素不一样 ， 否则有可能两个集合的根节点的值相同 ， 但是它们的子节点并不属于同一个集合！这可能会带来判断错误！
下面是具体的代码实现：
#includeusing namespace std;const int N = 1e5+10;int n,m;int p[N];int find(int x){//这里千万不能写成p[x] = find(x)！这样会陷入死递归！！一直出不来if(p[x]!=x)p[x] = find(p[x]);return p[x];}int main(){scanf("%d%d",&n,&m);for(int i = 0;i
延伸
这道题可以用并查集维护连通块 。需求1、2跟前面的是一样的 。而对于需求（3） ， 我们需要额外开辟一个记录连通块中点的数目的数组 ， 其中num[k]表示以k为根节点的连通块的点的数目 。（我们约定 ， 只有根节点处的num才有意义） 。初始时 ， 各个连通块只有一个点 ， 所以我们把num的各个位置初始值赋成1就好 。
#includeusing namespace std;const int N = 1e5+10;//size[k]表示k元素所在的连通块的点的个数 。我们规定只有根节点的size是有意义的 。int p[N],num[N];int find(int x){if(p[x]!=x) p[x] = find(p[x]);return p[x];}int main(){int n,m;scanf("%d%d",&n,&m);for(int i = 0;i
三、堆
堆是一棵完全二叉树 ， 其中小根堆指的是每个父节点都小于等于它的两个子节点的树 ， 大根堆相反 。那么我们可知 ， 小根堆的根节点就是这个堆的最小值 。
堆有两个基本操作：向上调整和向下调整 。后续的所有操作插入数据、求集合中的最小值、删除集合中的最小值、删除任意一个元素、修改任意一个元素都是它们的组合 。下面我们以小根堆为例说明 。
1.向下调整

文章插图
当我们把某个节点的值变大 ， 根据定义 ， 这时它的位置要下移 。但是在下移的过程中我们不能破坏堆的结构 ， 即仍然要保持父节点小于等于两个子节点 。向下调整的过程中每层要与两个节点比较 ， 找到三个点中的最小值 ， 该最小值与改变的节点交换位置 。

• 上一页
• 1
• 2
• 3
• 下一页

• 青岛火车站地址
• 江南客运站时刻表
• 零食站点
• 燕郊火车站
• 苏州客运总站
• 服务器安装网站流程图,服务器操作系统的安装流程图
• 石家庄北站
• 柳林火车站
• 贵阳汽车站
• 中 【C++从0到王者】第五站：类和对象const和取地址运算符重载