题目描述

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程equations[i]的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。 只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

题解

这一道题，显然是用并查集来解决，思路很简单，由于相等具有传递性，可以认为，一开始所有的字母变量都是独立的 集合，通过等式传递性，可以将这些相等的字母合并到同一个集合，最后看不等式中，是否存在连通的字母，如果存在 则表示等式方程不满足条件。

#include <vector>
#include <unordered_map>

class UnionFind {
public:
    UnionFind(int num) {
        for (int i = 0; i < num; ++i) {
            parent_.push_back(i);
        }
    }

    void unite(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        parent_[pRoot] = qRoot;
    }

    int find(int p) {
        if (p != parent_[p]) {
            parent_[p] = find(parent_[p]);
        }
        return parent_[p];
    }

private:
    std::vector<int> parent_;
};

class Solution {
public:
    bool equationsPossible(const std::vector<std::string>& equations) {
        // 26个小写字母
        UnionFind uf(26);
        for (const auto& e : equations) {
            if (e[1] == '!') {
                continue;
            }
            uf.unite(e[0] - 'a', e[3] - 'a');
        }
        for (const auto& e : equations) {
            if (e[1] == '=') {
                continue;
            }
            if (uf.find(e[0] - 'a') == uf.find(e[3] - 'a')) {
                return false;
            }
        }
        return true;
    }
};