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.