题目描述

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

题解

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

 1#include <vector>
 2#include <unordered_map>
 3
 4class UnionFind {
 5public:
 6    UnionFind(int num) {
 7        for (int i = 0; i < num; ++i) {
 8            parent_.push_back(i);
 9        }
10    }
11
12    void unite(int p, int q) {
13        int pRoot = find(p);
14        int qRoot = find(q);
15        if (pRoot == qRoot) {
16            return;
17        }
18        parent_[pRoot] = qRoot;
19    }
20
21    int find(int p) {
22        if (p != parent_[p]) {
23            parent_[p] = find(parent_[p]);
24        }
25        return parent_[p];
26    }
27
28private:
29    std::vector<int> parent_;
30};
31
32class Solution {
33public:
34    bool equationsPossible(const std::vector<std::string>& equations) {
35        // 26个小写字母
36        UnionFind uf(26);
37        for (const auto& e : equations) {
38            if (e[1] == '!') {
39                continue;
40            }
41            uf.unite(e[0] - 'a', e[3] - 'a');
42        }
43        for (const auto& e : equations) {
44            if (e[1] == '=') {
45                continue;
46            }
47            if (uf.find(e[0] - 'a') == uf.find(e[3] - 'a')) {
48                return false;
49            }
50        }
51        return true;
52    }
53};