Leetcode - 990: equations of satisfiability

题目

题目连接

给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一：“a==b” 或 “a!=b”.在这里,a 和 b 是小写字母（不一定不同）,表示单字母变量名.

只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false.

示例 1：

输入：["a==b","b!=a"]
输出：false
解释：如果我们指定,a = 1 且 b = 1,那么可以满足第一个方程,但无法满足第二个方程.没有办法分配变量同时满足这两个方程.

示例 2：

输入：["b==a","a==b"]
输出：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程.

示例 3：

输入：["a==b","b==c","a==c"]
输出：true

示例 4：

输入：["a==b","b!=c","c==a"]
输出：false

示例 5：

输入：["c==c","b==d","x!=z"]
输出：true

解题

The concept of check union 来源

方法一：并查集

参考链接
due to equal elements,放到一个集合,So there needs to be multiple collections.
If the equals sign is involved in associating two sets,Then it will also involve the merge operation of the collection.
for unequal elements,The set can be determined,if within a set,就返回false

下图是 Full compression of the tree structure,也就是在findinside the function.

class UnionFind{
    
private:
    vector<int> parent;
public:
    UnionFind(){
    
        parent.resize(26);
        iota(parent.begin(),parent.end(),0);
    }
    int find(int index){
    //查找根节点
        if(index==parent[index]) return index;
        parent[index]=find(parent[index]);//The parent node of all association nodes points to the root node of the association
        return parent[index];
    }

    void unite(int index1,int index2){
    //关联（Point the parent of the root node of the first variable to the root node of the second variable）
        parent[find(index1)]=find(index2);
    }

};


class Solution {
    
public:
    bool equationsPossible(vector<string>& equations) {
    
        UnionFind uf;
        for(string& s:equations){
    
            if(s[1]=='='){
    
                uf.unite(s[0]-'a',s[3]-'a');
            }
        }
        for(string& s:equations){
    
            if(s[1]=='!'){
    
                if(uf.find(s[0]-'a')==uf.find(s[3]-'a')) return false;
            }
        }
        return true;
    }
};