Solution
Approach 1: Connected Components
Intuition
All variables that are equal to each other form connected components. For example, if a=b, b=c, c=d
then a, b, c, d
are in the same connected component as they all must be equal to each other.
Algorithm
First, we use a depth first search to color each variable by connected component based on these equality equations.
After coloring these components, we can parse statements of the form a != b
. If two components have the same color, then they must be equal, so if we say they can't be equal then it is impossible to satisfy the equations.
Otherwise, our coloring demonstrates a way to satisfy the equations, and thus the result is true.
Complexity Analysis

Time Complexity: where is the length of
equations
. 
Space Complexity: , assuming the size of the alphabet is .
Analysis written by: @awice.