leetcode

0 class UnionFind {

1 vector<int> root, rank;

2

3 public:

4 UnionFind(int n) : root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); }

5

6 int find(int x) {

7 if (x == root[x]) return x;

8 return root[x] = find(root[x]);

9 }

10

11 void join(int x, int y) {

12 x = find(x), y = find(y);

13

14 if (x != y) {

15 if (rank[x] > rank[y]) swap(x, y);

16 root[y] = x;

17 rank[x] += x == y;

18 }

19 }

20 };

21

22 class Solution {

23 public:

24 bool equationsPossible(vector<string> &equations) {

25 UnionFind uf(26);

26 for (auto &s : equations)

27 if (s[1] == '=') uf.join(s[0] - 'a', s[3] - 'a');

28

29 for (auto &s : equations)

30 if (s[1] == '!' && uf.find(s[0] - 'a') == uf.find(s[3] - 'a')) return false;

31 return true;

32 }

33 };