算法（50）-并查集（1）-C++

并查集提供两种操作：    
                         1.查询a,b是否属于一个集合  bool issamset(V O1,V O2);
                         2.把a所在集合和b所在集合合并。操作的是元素，合并的是元素所在的集合。union(V O1,V O2);

template <class V>
class Element
{
public: V value;

        Element(V value)
        {
            this.value = value;
        }

};
template <class V>
class UnionFindSet
{
public:
    unordered_map<V, Element<V>>          elementMap;           //1、每个节点<值，节点>
    unordered_map<Element<V>, Element<V>> fatherMap;            //2.集合    <子节点,父节点>
    unordered_map<Element<V>, int>        sizeMap;              //3.集合头节点    sizeMap    集合大小决定谁挂谁  只包含头节点信息的  key 是集合的头节点（代表节点）
                                                                // key:代表节点 a ;value  个数  3 
    UnionFindSet(list<V> list);
    Element<V> findHead(Element<V> element);
    boolean isSameSet(V a, V b);
    void union_test(V a, V b);

};


template <class V>
UnionFindSet<V>::UnionFindSet(list<V> inlist)
{          
    for (V value : inlist)
    {
        Element<V> m_element = new Element<V>(value);
        elementMap.insert(value, m_element);  //   只是自己
        fatherMap.insert(m_element, m_element); //   指向自己
        sizeMap.insert(m_element, 1);         //初始化 只是自己
    }
}
template <class V>
Element<V> UnionFindSet<V>::findHead(Element<V> element)    //目的，从输入参数 elemnet 出发，一直往上找，一直找到不能找 返回 找其代表节点
{
    stack<Element<V>> path;                           // 1.记录往上沿途的点
    while (element != fatherMap.find(element))        // 2.父亲！=自己  往上到不能再往上了
    {
        path.push(element);                             //2.1添加路径  沿途的点
        element = fatherMap.find(element);              //2.2来到自己父亲的位置
    }
    //代表节点
    while (!path.isEmpty())                                   //
    {
        fatherMap.insert(make_pair(path.top(), element));     //  修改沿途 所有节点的代表节点 
        path.pop();
    }
    return element;
}
//是否是一个集合的
template <class V>
boolean UnionFindSet<V>::isSameSet(V a, V b)
{
    if (elementMap.count(a) && elementMap.count(b))
    {
        return findHead(elementMap.find(a)) == findHead(elementMap.find(b));
    }
    return false;
}

//合并函数
template <class V>
void UnionFindSet<V>::union_test(V a, V b)
{
    if (elementMap.count(a) && elementMap.count(b))          //  1.判断样本注册是否过，就是初始化过
    {
        Element<V> aF = findHead(elementMap.find(a));         // 2.a，找其代表节点
        Element<V> bF = findHead(elementMap.find(b));         //   b，找其代表节点
                                                              //3. 重定向 ，大集合给big  小集合给small
        if (aF != bF)                                         // 不同的时候返回 同的时候表示两个已经合并  
        {
            //  Element<V> m_big = rankMap.find(aF) >= rankMap.find(bF) ? aF : bF;//1.判断 a b 所属集合的大小
            //  Element<V> m_small= m_big == aF ? bF : aF;                      // 2.大的给 big  小的给small
            Element<V> m_big = NULL;
            Element<V> m_small = NULL;
            if (sizeMap.find(aF)>= sizeMap.find(bF))
            {
                m_big = aF;
                m_small = bF;
            }
            else
            {
                m_big = bF;
                m_small = aF;
            }
                fatherMap.insert(m_small, m_big);                                // 3. 修改 fatherMap  small的代表节点改为 big
                sizeMap.insert(m_big, sizeMap.find(aF)+ sizeMap.find(bF));    // 4. 修改rankMap放入 大的删掉小的 
                sizeMap.erase(m_small);                                        // 5. 删掉small
        }
    }
}