 # LeetCode Satisfiability of Equality Equations Solution

You are given an array of strings `equations` that represent relationships between variables where each string `equations[i]` is of length `4` and takes one of two different forms: `"xi==yi"` or `"xi!=yi"`.Here, `xi` and `yi` are lowercase letters (not necessarily different) that represent one-letter variable names.

Return `true` if it is possible to assign integers to variable names so as to satisfy all the given equations, or `false` otherwise.

Example 1:
Input: `equations = ["a==b","b!=a"]`
Output: `false`
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second. There is no way to assign the variables to satisfy both equations.

Example 2:
Input: `equations = ["b==a","a==b"]`
Output: `true`
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

Constraints:

• `1 <= equations.length <= 500`
• `equations[i].length == 4`
• `equations[i]` is a lowercase letter.
• `equations[i]` is either `'='` or `'!'`.
• `equations[i]` is `'='`.
• `equations[i]` is a lowercase letter.

## Solution

We will use DSU for this question with two passes on `equations`.

In the first pass, we join the variables that are equal into one component. In the second pass, we check whether two variables in an inequality expression are indeed in different components. If we arrive at a contradition, then the equality equations are not satisfiable.

#### Implementation

``````1def equationsPossible(self, equations: List[str]) -> bool:
2    equality = {}
3    def find(x):
4        y = equality.get(x, x)
5        if y != x:
6            equality[x] = y = find(y)
7        return y
8    def union(x, y):
9        equality[find(x)] = find(y)
10
11    for eq in equations:
12        if eq == '=':
13            union(eq, eq)
14    for eq in equations:
15        if eq == '!' and find(eq) == find(eq):
16            return False
17    return True    ``````