설명

예 1:

Input: equations = ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.
There is no way to assign the variables to satisfy both equations.

예 2:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

제약:

솔루션

솔루션 1

직관

암호

class Solution {
private:
    int p[26];

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
public:
    bool equationsPossible(vector<string>& equations) {
        for (int i = 0; i < 26; i++) {
            p[i] = i;
        }
        for (string& equation : equations) {
            int a = equation[0] - 'a', b = equation[3] - 'a';
            if (equation[1] == '=') {
                p[find(a)] = find(b);
            }
        }

        for (string& equation : equations) {
            int a = equation[0] - 'a', b = equation[3] - 'a';
            if (equation[1] == '!' && find(a) == find(b)) {
                return false;
            }
        }
        return true;

    }
};

복잡성