leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0990.cpp (814B)

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 };