990. 等式方程的可满足性

骑猪看日落 2022-12-12 15:19 88阅读 0赞

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 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

提示：

1 <= equations.length <= 500  
equations\[i\].length == 4  
equations\[i\]\[0\] 和 equations\[i\]\[3\] 是小写字母  
equations\[i\]\[1\] 要么是 '='，要么是 '!'  
equations\[i\]\[2\] 是 '='

来源：力扣（LeetCode）  
[题目链接][Link 1]

代码：

class Solution {
    public:
    int F[10001];
    int find(int x) {
        int a = x;
        while(x != F[x])
            x = F[x];
        while(a != F[a]) {
            int z = a;
            a = F[a];
            F[z] = x;
        }
        return x;
    }
    void Union(int x,int y)
    {
        int fx=find(x);
        int fy=find(y);
        if(fx!=fy)
            {
                F[fx]=fy;
            }
    }
        bool equationsPossible(vector<string>& equations) {
            int i;
        for(i=1;i<=10000;i++)
            F[i]=i;
        for(i=0;i<equations.size();i++){
            if(equations[i][0]==equations[i][3]&&equations[i][1]=='!'){
                return false;
            }
            if(equations[i][1]=='='){
                Union(equations[i][0],equations[i][3]);
            }
        }
        for(i=0;i<equations.size();i++){
            if(equations[i][1]=='!'){
                int root1=find(equations[i][0]);
                int root2=find(equations[i][3]);
                if(root1==root2){
                    return false;
                }
            }
        }
        return true;
        }
    };

[Link 1]: https://leetcode-cn.com/problems/satisfiability-of-equality-equations/