并查集中的元素个数

……怎么样去求一个并查集中某一个集合的元素个数呢？

究竟在找的时候递归得到答案，并完之后遍历，还是一个一个在合并的时候去查找呢？

基本思想

初始化时将与father数组对应的num数组中的元素全部变为1
每一次合并时将被合并集合元素数加到合并到的集合的父节点的num中

=> father[x] = y; //x的爸爸是y
=> num[y] += num[x]; //爸爸的元素数再加上孩子的元素数

对现有max(初始化为0)和当前集合元素数取max 取最大元素数，减少计算量
查询元素所在集合的元素数即访问其父根节点的num数组值

=> num[find(x)]

示例源码

class Unionfind
{
  private:
    vector<int> father;
    vector<int> num;
    int max_num = 0;

  public:
    Unionfind(int max_size) : father(std::vector<int>(max_size+1)),num(std::vector<int>(max_size+1))
    {
        for (int i = 0; i <= max_size; i++)
        {
            father[i] = i;
            num[i] = 1;
        }
    }

    int find(int x)
    {
        return father[x] == x ? x : father[x] = find(father[x]);
    }

    void merge(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        father[x] = y;
        num[y] += num[x];
        max_num = max(max_num,num[y]);
        //此处仅在遍历时更新，倘若没有合并操作则可能出现错误
    }

    //防止没有合并操作错误，保证得到最大元素数的遍历
    int max_num_of_items()
    {
        for(int i = 0; i < num.size(); i++)
            max_num = max(max_num,num[i]);
        return max_num;
    }

    int set_num_of(int x)
    {
        return num[find(x)];
    }
};