【高效管理集合】并查集的实现与应用-并查集的应用

省份的数量

题目信息：

示例：

代码展示：

class Solution 
{
public:
    //给的是城市的下标
    int findCircleNum(vector<vector<int>>& isConnected) 
    {
        //vector模拟并查集行为
        vector<int> ufs(isConnected.size(),-1);
        //需要用引用进行捕获
        auto FindRoot=[&ufs](int x){
            while(ufs[x]>=0) x=ufs[x];
            return x;
        };
        //遍历二维数组
        for(size_t i=0;i<isConnected.size();i++)
        {
            for(size_t j=0;j<isConnected[i].size();j++)
            {
                //如果这两个城市相连，就进入一个集合
                if(isConnected[i][j]==1)
                {
                    int root1=FindRoot(i),root2=FindRoot(j);
                    if(root1!=root2)
                    {
                        //将两个合并
                        ufs[root1]+=ufs[root2];
                        //存父亲的下标
                        ufs[root2]=root1;
                    }
                }
            }
        }
        int n=0;
        for(auto e:ufs)
            if(e<0)n++;
        return n;
    }
};

等式方程的可满足性

题目信息：

示例：

代码展示：

class Solution 
{
public:
    bool equationsPossible(vector<string>& equations) 
    {
        //开26个空间
        vector<int> ufs(26,-1);
        auto FindRoot=[&ufs](int x){
            while(ufs[x]>=0) x=ufs[x];
            return x;
        };
        //第一遍找相等的字母
        for(auto& str:equations)
        {
            if(str[1]=='=')
            {
                int root1=FindRoot(str[0]-'a'),root2=FindRoot(str[3]-'a');
                if(root1!=root2)
                {
                    ufs[root1]+=ufs[root2];
                    ufs[root2]=root1;
                }
            }
        }
        //第二遍找不同的字母，如果不同的字母在一个集合中，返回false
        for(auto& str:equations)
        {
            if(str[1]=='!')
            {
                int root1=FindRoot(str[0]-'a'),root2=FindRoot(str[3]-'a');
                if(root1==root2) return false;
            }
        }
        return true;
    }
};