Approach 1: Connected Components
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.
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.
Time Complexity: where is the length of
Space Complexity: , assuming the size of the alphabet is .
Analysis written by: @awice.