All problems

Satisfiability of Equality Equations

Medium · union find

You are given a list of equations. Each one is a string made of two names joined by either == ("is equal to") or != ("is different from"), for example "ab==c" or "x!=y". A name is one to three lowercase letters. The same name always stands for the same whole number, and a name may appear in many equations, on either side.

Return true if you can give every name a whole number so that all the equations are true at the same time, and false otherwise.

Examples

Example 1

Input: equations = ["a==b", "b==c", "a!=d"]

Output: true

Give a, b and c the number 1 and d the number 2.

Example 2

Input: equations = ["a==b", "b==c", "c!=a"]

Output: false

a equals b and b equals c, so a equals c, which contradicts c != a.

Example 3

Input: equations = ["x!=y", "y!=z", "z!=x"]

Output: true

Three different numbers satisfy all three.

Constraints

• 1 <= len(equations) <= 1000
• Each equation has the form name==name or name!=name, where each name is 1 to 3 lowercase letters.
• The two names of one equation may be the same.