Cacher is the code snippet organizer for pro developers

/**
 * @brief 并查集算法，Quick-Find
 */
class DisjointSet
{
public:
    /**
     * 构造函数，并设置元素个数
     * @param[in] size 初始化的并查集，设置的元素个数
     */
    DisjointSet(int size)
    {
        id = new int[size];
        for (int i = 0; i < size; ++i)
        {
            makeSet(i);
        }
        num = size;
    }

    /**
     * @brief 析构函数
     */
    ~DisjointSet()
    {
        delete[] id;
    }

    /**
     * @brief 将包含p和q的两个动态集合（表示为Sp和Sq）合并成一个新的集合
     * @param[in] p 需要进行合并的其中一个集合元素
     * @param[in] q 需要进行合并的其中一个集合元素
     */
    inline void unionElem(int p, int q)
    {
        int pID = find(p);
        int qID = find(q);
        if (pID == qID) return;
        //遍历一次，该表所有的组号，并该表其中一组的组号，使两组合并
        for (int i = 0; i < num; ++i)
        {
            if (id[i] == pID)
                id[i] = qID;
        }
        --num;
    }

    /**
     * @brief 找到元素p的代表
     * @param[in] p需要获取代表的元素
     * @return 元素p的代表
     */
    inline int find(int p)
    {
        return id[p];
    }

    /**
     * @brief 获取集合的个数
     * @return 当前集合的个数
     */
    inline int getSetNum()
    {
        return num;
    }

private:
    /**
     * @brief 建立一个新的集合，它的唯一成员（因而为代表）是p
     * @param p 创建集合的唯一成员元素
     */
    inline void makeSet(int p)
    {
        id[p] = p;
    }

private:
    int * id;   //并查集的元素
    int num;    //并查集的组数
};

/**
 * @brief 并查集算法，Union by rank With Path Compression
 */
class DisjointSet
{
public:
    /**
     * 构造函数，并设置元素个数
     * @param[in] size 初始化的并查集，设置的元素个数
     */
    DisjointSet(int size)
    {
        id = new int[size];
        weight = new int[size];
        for (int i = 0; i < size; ++i)
        {
            makeSet(i);
        }
        num = size;
    }

    /**
     * @brief 析构函数
     */
    ~DisjointSet()
    {
        delete[] id;
        delete[] weight;
    }

    /**
     * @brief 将包含p和q的两个动态集合（表示为Sp和Sq）合并成一个新的集合
     * @param[in] p 需要进行合并的其中一个集合元素
     * @param[in] q 需要进行合并的其中一个集合元素
     */
    inline void unionElem(int p, int q)
    {
        // Give p and q the same root.  
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot)
            return;
        //将高度较低的树做为高度较低的树的子树
        if (weight[pRoot] < weight[qRoot])
        {
            id[pRoot] = qRoot;
        }
        else
        {
            id[qRoot] = pRoot;
            if (weight[pRoot] == weight[qRoot])
                ++weight[pRoot];
        }
        --num;
    }

    /**
     * @brief 找到元素p的代表
     * @param[in] p需要获取代表的元素
     * @return 元素p的代表
     */
    inline int find(int p)
    {
        if (p != id[p])
            id[p] = find(id[p]);
        return id[p];
    }

    /**
     * @brief 获取集合的个数
     * @return 当前集合的个数
     */
    inline int getSetNum()
    {
        return num;
    }

private:
    /**
     * @brief 建立一个新的集合，它的唯一成员（因而为代表）是p
     * @param p 创建集合的唯一成员元素
     */
    inline void makeSet(int p)
    {
        id[p] = p;
        weight[p] = 1;  //每个节点初始化权重都是1（都只含有一层）
    }

private:
    int * id;       //并查集的元素
    int * weight;   //对应一棵树的高度，并将其作为权重,即rank
    int num;        //并查集的组数
};