aboutsummaryrefslogtreecommitdiff
path: root/satisfiability_eqaulity.cpp
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";
}