## Algorithm

Problem Name: 990. Satisfiability of Equality Equations

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 `'='`.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean equationsPossible(String[] equations) {
List[] graph = new ArrayList;
for (int i = 0; i < 26; i++) {
graph[i] = new ArrayList<>();
}
for (String equation : equations) {
if (equation.charAt(1) == '=') {
int first = equation.charAt(0) - 'a';
int second = equation.charAt(3) - 'a';
}
}
int[] color = new int;
Arrays.fill(color, -1);
for (int i = 0; i < 26; i++) {
if (color[i] == -1) {
dfs(i, i, color, graph);
}
}
for (String equation : equations) {
if (equation.charAt(1) == '!') {
int first = equation.charAt(0) - 'a';
int second = equation.charAt(3) - 'a';
if (color[first] == color[second]) {
return false;
}
}
}
return true;
}

private static void dfs(int node, int nodeColor, int[] color, List[] graph) {
if (color[node] == -1) {
color[node] = nodeColor;
for (int neighbor : graph[node]) {
dfs(neighbor, nodeColor, color, graph);
}
}
}
}
``````
Copy The Code &

Input

cmd
equations = ["a==b","b!=a"]

Output

cmd
false

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const equationsPossible = function(equations) {
const uf = new Array(26).fill(0);
const aCode = ('a').charCodeAt(0)

for (let i = 0; i < 26; ++i) uf[i] = i;
for (let e of equations)
if (e.charAt(1) === '=')
uf[find(e.charCodeAt(0) - aCode)] = find(e.charCodeAt(3) - aCode);
for (let e of equations)
if (e.charAt(1) === '!' && find(e.charCodeAt(0) - aCode) === find(e.charCodeAt(3) - aCode))
return false;
return true;

function find(x) {
if (x != uf[x]) uf[x] = find(uf[x]);
return uf[x];
}
};
``````
Copy The Code &

Input

cmd
equations = ["a==b","b!=a"]

Output

cmd
false

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
def uf(c):
return uf(parent[ord(c) - ord('a')]) if parent[ord(c) - ord('a')] != c else ord(c) - ord('a')
parent = [c for c in string.ascii_lowercase]
for eq in equations:
if eq == '=':
parent[uf(eq)] = parent[uf(eq[-1])]
for eq in equations:
if eq == '!' and parent[uf(eq)] == parent[uf(eq[-1])]:
return False
return True
``````
Copy The Code &

Input

cmd
equations = ["b==a","a==b"]

Output

cmd
true