题目描述

给定一个公式数组，每一个公式表示两个变量的关系。每一个字符串 equations[i] 长度为 4，有两种形式，"a==b" 或 "a!=b"。这里 a 和 b 都是小写字母（不一定不同），表示一个变量名。

返回 true 当且仅当可以将变量赋值整数，使得满足所有的公式。

样例

输入：["a==b","b!=a"]
输出：false
解释：如果我们给 a = 1 和 b = 1，则第一个公式可以被满足，但第二个无法被满足。
没有办法赋值变量同时满足两个公式。

输入：["b==a","a==b"]
输出：true
解释：赋值 a = 1 和 b = 1 可以满足所有公式。

输入：["a==b","b==c","a==c"]
输出：true

输入：["a==b","b!=c","c==a"]
输出：false

输入：["c==c","b==d","x!=z"]
输出：true

注意

• 1 <= equations.length <= 500
• equations[i].length == 4
• equations[i][0] 和 equations[i][3] 都是小写字母。
• equations[i][1] 是 '=' 或 '!'。
• equations[i][2] 是 '='。

算法

(并查集) $O(n)$

1. 第一次遍历相等判定的公式，然后将对应的变量放入到同一集合中。
2. 第二次遍历所有不等的公式，如果对应的变量出现在了同一集合中，则说明不合法，返回 false。
3. 如果没有矛盾，返回 true。

时间复杂度

• 假设并查集的操作时间复杂度为常数，则算法只需要遍历所有的公式，故时间复杂度为 $O(n)$。

空间复杂度

• 由于只有 26 个字母，所以只需要常数的空间。

C++ 代码

class Solution {
public:
    vector<int> f, sz;
    int find(int x) {
        return x == f[x] ? x : f[x] = find(f[x]);
    }

    void uni(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy)
            return;
        if (sz[fx] < sz[fy]) {
            f[fx] = fy;
            sz[fy] += sz[fx];
        }
        else {
            f[fy] = fx;
            sz[fx] += sz[fy];
        }
    }

    bool equationsPossible(vector<string>& equations) {
        f.resize(26);
        sz.resize(26);
        for (int i = 0; i < 26; i++) {
            f[i] = i;
            sz[i] = 1;
        }

        for (auto &s : equations) {
            if (s[1] == '=') {
                int x = s[0] - 'a', y = s[3] - 'a';
                uni(x, y);
            }
        }

        for (auto &s : equations) {
            if (s[1] == '!') {
                int x = s[0] - 'a', y = s[3] - 'a';
                int fx = find(x), fy = find(y);
                if (fx == fy)
                    return false;
            }
        }

        return true;
    }
};