blob: b0a1f8b32d58e74b1bd1d73d8d381614d095557c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include "leetcode.h"
class Solution {
public:
bool equationsPossible(vector<string> &equations) {
for (int i = 0; i < 26; ++i)
uf[i] = i;
for (string e : equations)
if (e[1] == '=')
uf[find(e[0] - 'a')] = find(e[3] - 'a');
for (string e : equations)
if (e[1] == '!' && find(e[0] - 'a') == find(e[3] - 'a'))
return false;
return true;
}
private:
int uf[26];
int find(int x) {
if (x != uf[x])
uf[x] = find(uf[x]);
return uf[x];
}
};
int main() {
Solution obj;
vector<string> equations = {"a==b", "b!=a"};
if (obj.equationsPossible(equations))
cout << "true";
else
cout << "false";
}
|