Satisfiability of Equality Equations

Problem Id: 990 Difficulty: Medium


Intuition

Solution


class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        indexes = {}
        count = 0
        for expression in equations:
            if '==' in expression:
                p, q = expression.split('==')
            else:
                p, q = expression.split('!=')
            for c in [p, q]:
                if c not in indexes:
                    indexes[c] = count
                    count += 1

        dsu = DSU(len(indexes))
        for expression in equations:
            if '==' in expression:
                p, q = expression.split('==')
                dsu.union(indexes[p], indexes[q])

        for expression in equations:
            if '!=' in expression:
                p, q = expression.split("!=")
                if dsu.find(indexes[p]) == dsu.find(indexes[q]):
                    return False
        return True