aboutsummaryrefslogtreecommitdiff
path: root/satisfiability_eqaulity.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'satisfiability_eqaulity.cpp')
-rw-r--r--satisfiability_eqaulity.cpp33
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";
+}