并查集是一种基础数据结构，主要解决连通性问题。这里不对并查集的概念做详细的解释，主要是介绍并查集的两种实现。

vector 实现

  参考《算法》 第四版中介绍的路径压缩的 quick-union 算法。每次查询时，把查询路径上的所有节点都指向查询的结果（即根节点），得到几乎完全扁平的树。
  考虑到线程安全的问题，写了一个 const 成员函数 Find()；对树的路径压缩的过程在 Union 的时候实现。

Header

#include <vector>
using namespace std;

class vectorBase : public vector<unsigned>
{
public:
    void        init(unsigned sz);
    unsigned    Find(unsigned index) const;
    void        Union(unsigned index1, unsigned index2);

private:
    int         updateFind(unsigned index);
};

Source

void vectorBase::init(unsigned sz)
{
    resize(sz);
    for (int i = 0; i < sz; ++i) {
        (*this)[i] = i;
    }
}

unsigned vectorBase::Find(unsigned index) const
{
    unsigned p = (*this)[index];
    while (p != index) {
        index = p;
        p = (*this)[p];
    }
    return index;
}

void vectorBase::Union(unsigned index1, unsigned index2)
{
    (*this)[updateFind(index1)] = updateFind(index2);
}

int vectorBase::updateFind(unsigned index)
{
    if ((*this)[index] != index)
        (*this)[index] = updateFind((*this)[index]);

    return (*this)[index];
}

unordered_map 实现

  vector 实现的并查集非常简单高效，但是只能用于整数；unordered_map 实现的并查集可以用于任意类型的数据，只要该数据类型有计算 hash 值的函数就行。

#include <unordered_map>
#include <unordered_set>
using namespace std;

template <typename T>
struct myHash
{
    size_t  operator() (const T& t) const {
        return t.hashValue();
    }
};

template <typename T>
class mapBase : public unordered_map<T, T, myHash<T>>
{
    using unordered_multimap<T, T, myHash<T>>::find;
    using unordered_multimap<T, T, myHash<T>>::end;
    using unordered_multimap<T, T, myHash<T>>::insert;

public:
    void    Union(const T& t1, const T& t2);
    T       Find(const T& t) const;

private:
    T       updateFind(const T& t);
};

template <typename T>
inline void mapBase<T>::Union(const T &t1, const T &t2)
{
    const T& l1 = updateFind(t1);
    const T& l2 = updateFind(t2);
    if (l1 != l2)
        insert({l1, l2});
}

template <typename T>
inline T mapBase<T>::Find(const T &t) const
{
    T res = t;
    auto it = find(t);
    while (it != end()) {
        res = (*it).second;
        it = find(res);
    }
    return res;
}

template <typename T>
inline T mapBase<T>::updateFind(const T &t)
{
    T res = t;
    unordered_set<T> visited;
    auto it = find(t);
    while (it != end()) {
        visited.insert((*it).first);
        res = (*it).second;
        it = find(res);
    }

    for (auto& v :visited) {
        auto iter = find(v);
        (*iter).second = res;
    }

    return res;
}

总结

  并查集的实现是多种多样的，这里只是介绍了其中的两种；比如也可以用 map 实现，只是这样每一次查询的时间从 O(1) 变成了 O(logn)。具体到项目中，要根据实际情况修改代码。