# 990. Satisfiability of Equality Equations

Given an array equations of strings that represent relationships between variables, each string `equations[i]` has length `4` and takes one of two different forms: `"a==b"` or `"a!=b"`.  Here, `a` and `b` are lowercase letters (not necessarily different) that represent one-letter variable names.

Return `true` if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

Example 1:

``````Input: ["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.
``````

Example 2:

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

Example 3:

``````Input: ["a==b","b==c","a==c"]
Output: true
``````

Example 4:

``````Input: ["a==b","b!=c","c==a"]
Output: false
``````

Example 5:

``````Input: ["c==c","b==d","x!=z"]
Output: true
``````

Note:

1. `1 <= equations.length <= 500`
2. `equations[i].length == 4`
3. `equations[i][0]` and `equations[i][3]` are lowercase letters
4. `equations[i][1]` is either `'='` or `'!'`
5. `equations[i][2]` is `'='`

``````class Solution {
public:
bool equationsPossible(vector<string>& equations) {
unordered_map<char, unordered_set<char>> g;
for (auto eq : equations) {
if (eq[1] == '!') continue;
g[eq[0]].insert(eq[3]);
g[eq[3]].insert(eq[0]);
}
for (auto eq : equations) {
if (eq[1] == '=') continue;
unordered_set<char> visited;
if (!check(g, eq[0], eq[3], visited)) return false;
}
return true;
}
bool check(unordered_map<char, unordered_set<char>>& g, char cur, char target, unordered_set<char>& visited) {
if (cur == target || g[cur].count(target)) return false;
for (char c : g[cur]) {
if (visited.count(c)) continue;
visited.insert(c);
if (!check(g, c, target, visited)) return false;
}
return true;
}
};
``````

``````class Solution {
public:
bool equationsPossible(vector<string>& equations) {
vector<int> root(26);
for (int i = 0; i < 26; ++i) root[i] = i;
for (string eq : equations) {
if (eq[1] == '!') continue;
root[find(root, eq[0] - 'a')] = find(root, eq[3] - 'a');
}
for (string eq : equations) {
if (eq[1] == '=') continue;
if (find(root, eq[0] - 'a') == find(root, eq[3] - 'a')) return false;
}
return true;
}
int find(vector<int>& root, int x) {
return root[x] == x ? x : find(root, root[x]);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/990

Redundant Connection II

Friend Circles

Graph Valid Tree

https://leetcode.com/problems/satisfiability-of-equality-equations/

https://leetcode.com/problems/satisfiability-of-equality-equations/discuss/234474/C%2B%2B-7-lines-with-picture-union-find

https://leetcode.com/problems/satisfiability-of-equality-equations/discuss/234486/JavaC%2B%2BPython-Easy-Union-Find

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation