# 990.Satisfiability of Equality Equations

\#990 Satisfiability of Equality Equations 难度:Medium

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

并查集。

```
class Solution {
vector<int>var;
public:
Solution(){
    var.resize(26);
    iota(var.begin(), var.end(),0);
}
int getInd(int index)
{
    if(index == var[index]) return index;
    return getInd(var[index]);
}
void unite(int index1, int index2)
{
    var[getInd(index1)] = var[getInd(index2)];
}

    bool equationsPossible(vector<string>& equations) {
        for(auto s: equations)
        {
            if(s[1] == '=')
            unite(s[0]-'a', s[3]-'a');
        }
        for(auto s:equations)
        {
            if(s[1]=='!')
            if(getInd(s[0]-'a') == getInd(s[3]-'a')) return false;
        }

        return true;
    }
};
```

> 执行用时 :8 ms, 在所有 C++ 提交中击败了86.19%的用户\
> 内存消耗 :11.1 MB, 在所有 C++ 提交中击败了50.00%的用户


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/990.satisfiability-of-equality-equations.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.