990. Satisfiability of Equality Equations

You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: “xi==yi” or “xi!=yi”.Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.

• Time : O(v + e)
• Space : O(v)
• 9min 8sec

class Solution {
    unordered_map<char, char> m;
    bool isEqualOperation(string& s) {
        return s[1] == '=';
    }
    char findParent(char ch) { //O(V) max, but after optimize, O(1)
        return m[ch] == ch ? ch : m[ch] = findParent(m[ch]);
    }
    void merge(char a, char b) {
        char pa = findParent(a), pb = findParent(b);
        m[pa] = m[pb] = min(pa, pb);
    }
    bool isSameGroup(char a, char b) {
        return findParent(a) == findParent(b);
    }
    
public:
    bool equationsPossible(vector<string>& equations) { //O(V + E)
        for(char ch = 'a'; ch <= 'z'; ch++) m[ch]=ch;
        vector<pair<char, char>> notEqualPairs;
        for(auto& equation : equations) { //O(E)
            if(isEqualOperation(equation)) {
                merge(equation[0], equation[3]);
            } else {
                notEqualPairs.push_back({equation[0], equation[3]});
            }
        }
        
        for(auto [a, b] : notEqualPairs) { //O(E)
            if(isSameGroup(a,b)) return false;
        }
        return true;
    }
};