并查集基于size的优化

一、介绍及逻辑

1. 介绍
2. 在上一小节我们使用指针的方法将每一个元素都看作是一个节点，并且是节点指向另一个节点(包括自己)，在这一小节中我们将在此基础上进行优化。
3. 先来介绍一下什么是”size”
4. size : size[i] 是指用来记录以i为根节点的树所包含的节点个数，本质是一个数组
5. 逻辑
6. 先来看看下面的图片：
7. 现在需要将4，2连接起来，该怎么连？

方法一：如下图

方法二：如下图

很容易看出方法二更优，树的高度越高，对计算机的消耗也会越大，所以很明显方法二是有3层，而方法一有4层(一旦有大量的数据时，性能差别就会明显)； 所以我们使用size数组，就是在维护方法二。

二、代码实现

#include<cassert>
using namespace std;
namespace UF3 
{
    class UnionFind2 
    {
        private:
        // 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树  
        // parent[i]表示第i个元素所指向的父节点  
        int *parent;
        int *size;  //size用来记录节点的个数  
        int count; //数据个数  
        public:UnionFind2(int count) 
        {
            parent = new int[count];
            size = new int[count];
            this->count = count;
            //初始化  
            for (int i = 0; i < count; i++) 
            {
                parent[i] = i;
                size[i] = 1;
            }
        }
        //析构函数~  
        UnionFind2() 
        {
            delete parent;
            delete size;
        }
        // 查找过程, 查找元素p所对应的集合编号// O(h)复杂度, h为树的高度  
        int find(int p) 
        {
            assert(p >= 0 && p <= count);
            // 不断去查询自己的父亲节点, 直到到达根节点  
            // 根节点的特点: parent[p] == p   
            while (p != parent[p])
                p = parent[p];
            return p;
        }
        // 查看元素p和元素q是否所属一个集合// O(h)复杂度, h为树的高度  
        bool isConnected(int p, int q) 
        {
            return find(p) == find(q);
        }
        //下面是size的核心：  
        // 合并元素p和元素q所属的集合// O(h)复杂度, h为树的高度    
        void unionElments(int p, int q) 
        {
            int pRoot = find(p);
            int qRoot = find(q);
            if (pRoot == qRoot) return;
            // 根据两个元素所在树的元素个数不同判断合并方向  
            // 将元素个数少的集合合并到元素个数多的集合上  
            if(size[pRoot] < size[qRoot]) 
            {
                parent[pRoot] = qRoot;
                size[qRoot] = +size[pRoot];
            }
            else 
            {   
                //size[pRoot] >= size[qRoot]
                parent[qRoot] = pRoot;
                size[pRoot] = +size[qRoot];
            }
        }
    };
}