diff options
Diffstat (limited to 'satisfiability_eqaulity.cpp')
-rw-r--r-- | satisfiability_eqaulity.cpp | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/satisfiability_eqaulity.cpp b/satisfiability_eqaulity.cpp new file mode 100644 index 0000000..b0a1f8b --- /dev/null +++ b/satisfiability_eqaulity.cpp @@ -0,0 +1,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"; +} |