# 990 Satisfiability of Equality Equations

## Problem Setting¶

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b". Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

### Example 1¶

Input: ["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: ["b==a","a==b"]

Output: true

Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

## Solution from superluminal¶

In :
# https://leetcode.com/superluminal/
class Solution(object):
def equationsPossible(self, equations):
"""
:type equations: List[str]
:rtype: bool
"""
uf = {}
def find(x):
if x not in uf: uf[x] = x
s = []
while uf[x] != x:
s.append(x)
x = uf[x]
for y in s: uf[y] = x
return x
for eq in equations:
if '==' not in eq: continue
a, b = find(eq), find(eq[-1])
# should compare rank but whatever
uf[a] = b
for eq in equations:
if '!=' not in eq: continue
a, b = find(eq), find(eq[-1])
if a == b: return False
return True


Step 1-1

• create function find
• determine if x exist in a dictionray uf
• If it does not exist, it will be stored as the key and the value
In :
uf = {}
def find(x):
if x not in uf: uf[x] = x
print(f'uf: {uf}')

return x

In :
find('a')

uf: {'a': 'a'}

Out:
'a'
In :
find('b')

uf: {'a': 'a', 'b': 'b'}

Out:
'b'

Step 1-2

• Keep append x to list s until the value and key is equal
In :
uf = {}
def find(x):
if x not in uf: uf[x] = x
s = []
print(f'uf: {uf}')
while uf[x] != x:
print(f'uf[x] != x: {x}')
s.append(x)
x = uf[x]
for y in s: uf[y] = x
return x

In :
eq = "a==b"
a, b = find(eq), find(eq[-1])
print(f'return value (a, b): {a, b}')
print(f'uf[a] = b: {uf[a], b}')
uf[a] = b
print(f'uf: {uf}')

uf: {'a': 'a', 'b': 'b', 'c': 'c'}
uf: {'a': 'a', 'b': 'b', 'c': 'c'}
return value (a, b): ('a', 'b')
uf[a] = b: ('a', 'b')
uf: {'a': 'b', 'b': 'b', 'c': 'c'}

In :
eq = "b==c"
a, b = find(eq), find(eq[-1])
print(f'uf[a] = b: {uf[a], b}')
uf[a] = b
print(f'uf: {uf}')

uf: {'a': 'b', 'b': 'b', 'c': 'c'}
uf: {'a': 'b', 'b': 'b', 'c': 'c'}
uf[a] = b: ('b', 'c')
uf: {'a': 'b', 'b': 'c', 'c': 'c'}

In [ ]:
eq = "b==c"
a, b = find(eq), find(eq[-1])
print(a, b)