# \[990]\[中等]\[并查集] 等式方程的可满足性

## 题目描述

[990. 等式方程的可满足性](https://leetcode-cn.com/problems/satisfiability-of-equality-equations/)

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

## 解题思路

### 并查集

非常标准的并查集.

首先每个字符串的两端变量, 都是小写字母, 因此点是有限的`26`个点. 然后关系只有相等和不等, 我们将相等的节点相连, 最后判断所有的不等式, 即两个点不在同一个集合中, 是否成立, 所有都满足则返回`True`.

值的注意的是, 如果列表中只有相等式, 没有不等式, 如例3, 肯定是满足的, 直接返回`True`.

```python
class Union:
    def __init__(self):
        self.parnet = list(range(26))

    @staticmethod
    def c2n(char):
        return ord(char) - 97

    @staticmethod
    def n2c(num):
        return chr(num + 97)

    def find(self, char):
        num = self.c2n(char)
        if self.parnet[num] == num:
            return num
        self.parnet[num] = self.find(self.n2c(self.parnet[num]))
        return self.parnet[num]

    def union(self, char1, char2):
        self.parnet[self.find(char1)] = self.find(char2)

    def connected(self, char1, char2):
        return self.find(char1) == self.find(char2)

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        u = Union()

        not_equal = []
        for s in equations:
            x, y, op = s[0], s[3], s[1]
            if op == '=':
                u.union(x, y)
            else:
                not_equal.append((x, y))

        for x, y in not_equal:
            if u.connected(x, y):
                return False
        return True
```


---

# 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://blessbingo.gitbook.io/garnet/suan-fa/bing-cha-ji/990-deng-shi-fang-cheng-de-ke-man-zu-xing.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.