# 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