高阶数据结构——并查集

1.并查集原理

        在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。

        举个例子：大学社团招新，一共招10人其中科协招4人，艺术团招3人，青协招3人，这10个人刚开始时相互并不认识，每个学生就是一个独立的团体，现在对这些学生编号：{0，1，2，3，4，5，6，7，8，9}；用下面的数组来存储这个小集体，数组中的数字代表该小集体的中的成员个数，负号表示为根节点

        他们准备去社团报道，每个社团的学生自发组织成小队一起去报道，于是：科协小队{0，6，7，8}，艺术团小队{1，4，9}，青协小队{2，3，5}，就这样10个人形成了3个小团体，假设左三个人为队长那么就有了下图

        如果用数组来表示就是下面这张图

        从上图可以看出：编号6，7，8同学属于0号小队，该小分队有4人，同理可以推出其他小队的人数和成员。

        仔细观察数组，可以得出以下结论：

                1.数组的下标对应集合中元素的编号

                2.数组中如果是负数代表根，数字代表该集合中元素的个数

                3.数组中如果为非负数，代表该元素的根在数组中的下标

        假设在社团工作一段时间后，1和8成为了好朋友，那么两个小圈子的学生相互介绍，最后这两个小圈子就融成了一个大圈子：

        通过上面的例子可知，并查集一般可以解决以下问题：

                1.查找元素属于那么集合：沿着数组表示树形关系往上一直找到根（即：树中元素为负数的位置）

                2.查看两个元素是否属于同一个集合：沿着数组表示的树形关系往 上一直找到树的根，如果根相同表明在同一个集合，否则不在

                3.将两个集合归并成一个集合：将两个集合中的元素合并或者将一个集合名称改成另一个集合的名称

                4.获取集合的个数：遍历数组，数组中元素为负数的个数即为集合的个数

2.并查集实现

#include <iostream>
#include <vector>


class union_find_set{
public:
    union_find_set(int size)
    :_ufs(size,-1){}
    
    int Findroot(int index)
    {
        while(_ufs[index] >= 0)
        {
            index = _ufs[index];
        }
        return index;
    }
    bool Union(int index1,int index2)
    {
        int root1 = Findroot(index1);
        int root2 = Findroot(index2);

        if(root1 == root2) return false;
        _ufs[root1] += _ufs[root2];
        _ufs[root2] = root1;
        return true;
    }
    size_t Count()
    {
        int count = 0;
        for(auto e:_ufs) if(e < 0) count++;
        return count;
    }
public:
    std::vector<int> _ufs;
};

测试模块代码：

#include "unionfindset.hpp"
#include <iostream>



int main()
{
    union_find_set test(10);
    test.Union(0,6);
    test.Union(0,7);
    test.Union(0,8);
    test.Union(1,4);
    test.Union(1,9);
    test.Union(2,3);
    test.Union(2,5);
    test.Union(8,1);
    for(auto ch:test._ufs) std::cout<<ch<<" ";
    return 0;
}

结果如下

3.并查集应用

省份数量：LCR 116. 省份数量 - 力扣（LeetCode）

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int len = isConnected.size();
        vector<int> _map(len,-1);
        auto FindRoot = [&_map](int x)->int{
            while(_map[x] >= 0) x = _map[x];
            return x; 
        };
        for(int i = 0;i<isConnected.size();i++)
        {
            for(int j = 0;j<isConnected[i].size();j++)
            {
                if(isConnected[i][j] == 1)
                {
                    int root1 = FindRoot(i), root2 = FindRoot(j);
                    if(root1 == root2) continue;
                    _map[root1] += _map[root2];
                    _map[root2] = root1;
                }
            }
        }
        int ret = 0;
        for(int i = 0;i<_map.size();i++) if(_map[i] < 0) ret++;
        return ret;
    }
};

等式方程的可满足性：990. 等式方程的可满足性 - 力扣（LeetCode）

简单讲讲思路：将相等的数据和不相等的数据视为两个子集如果两个子集有交集那么就是false否则就是true

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        vector<int> _map(26,-1);
        auto FindRoot = [&_map](int x)->int{
            while(_map[x] >=0) x = _map[x];
            return x;
        };

        for(auto ch:equations)
        {
            if(ch[1] == '=')
            {
                int root1 = FindRoot(ch[0]-'a'), root2 = FindRoot(ch[3]-'a');
                if(root1 != root2)
                {
                    _map[root1] += _map[root2];
                    _map[root2] = root1;
                }
            }
        }

        for(auto ch:equations)
        {
            if(ch[1] == '!')
            {
                int root1 = FindRoot(ch[0]-'a'), root2 = FindRoot(ch[3]-'a');
                if(root1 == root2) return false;
            }
        }
        return true;
    }
};