raghuvanshraj

990.cpp

Aug 4th, 2021
699
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:   vulkan
  3.  *    created:  13.08.2020 11:27:42 PM
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. class dsu_t {
  10.     int n;
  11.     vector<int> parent;
  12. public:
  13.     dsu_t(int n);
  14.     int find(int x);
  15.     void merge(int x, int y);
  16.     bool check(int x, int y);
  17. };
  18.  
  19. dsu_t::dsu_t(int n) {
  20.     this->n = n;
  21.     parent = vector<int>(n);
  22.     for (int i = 0; i <= n - 1; ++i) {
  23.         parent[i] = i;
  24.     }
  25. }
  26.  
  27. int dsu_t::find(int x) {
  28.     return x == this->parent[x] ? x : this->parent[x] = this->find(parent[x]);
  29. }
  30.  
  31. void dsu_t::merge(int x, int y) {
  32.     this->parent[this->find(x)] = this->find(y);
  33. }
  34.  
  35. bool dsu_t::check(int x, int y) {
  36.     return this->find(x) == this->find(y);
  37. }
  38.  
  39. bool equationsPossible(vector<string> &equations) {
  40.     dsu_t dsu(26);
  41.     for (string eq : equations) {
  42.         if (eq[1] == '=') {
  43.             int x = eq[0] - 'a', y = eq[3] - 'a';
  44.             dsu.merge(x, y);
  45.         }
  46.     }
  47.  
  48.     for (string eq : equations) {
  49.         if (eq[1] == '!') {
  50.             int x = eq[0] - 'a', y = eq[3] - 'a';
  51.             if (dsu.check(x, y)) {
  52.                 return false;
  53.             }
  54.         }
  55.     }
  56.  
  57.     return true;
  58. }
  59.  
  60. int main(int argc, char const *argv[]) {
  61.     int n;
  62.     cin >> n;
  63.     vector<string> equations(n);
  64.     for (int i = 0; i <= n - 1; ++i) {
  65.         cin >> equations[i];
  66.     }
  67.  
  68.     cout << equationsPossible(equations);
  69.  
  70.     return 0;
  71. }
RAW Paste Data