并查集

class UnionSet
{
public:
    UnionSet(size_t size)
        :_size(size)
    {
        _unionset.resize(size, -1);
    }

    void Combine(size_t pos1, size_t pos2)     //合并函数
    {
        int root1 = FindAncestor(pos1);
        int root2 = FindAncestor(pos2);
        _unionset[root1] += _unionset[root2];
        _unionset[root2] = root1;
    }

    int FindAncestor(size_t pos)     //寻找祖先节点的函数
    {
        while (_unionset[pos] >= 0)  //当某一元素为负数时说明，到了该集合的根节点了
        {
            pos = _unionset[pos];
        }
        return pos;
    }

protected:
    vector<int> _unionset;
    size_t _size;
};