# 990. Satisfiability of Equality Equations

• Time: $O(n\log n)$
• Space: $O(n)$
  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 34 35 36 37 38 39 40 41 class UnionFind { public: UnionFind(int n) : id(n) { iota(begin(id), end(id), 0); } void union_(int u, int v) { id[find(u)] = find(v); } int find(int u) { return id[u] == u ? u : id[u] = find(id[u]); } private: vector id; }; class Solution { public: bool equationsPossible(vector& equations) { UnionFind uf(26); for (const string& e : equations) if (e[1] == '=') { const int x = e[0] - 'a'; const int y = e[3] - 'a'; uf.union_(x, y); } for (const string& e : equations) if (e[1] == '!') { const int x = e[0] - 'a'; const int y = e[3] - 'a'; if (uf.find(x) == uf.find(y)) return false; } return true; } }; 
  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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 class UnionFind { public UnionFind(int n) { id = new int[n]; rank = new int[n]; for (int i = 0; i < n; ++i) id[i] = i; } public void unionByRank(int u, int v) { final int i = find(u); final int j = find(v); if (i == j) return; if (rank[i] < rank[j]) { id[i] = id[j]; } else if (rank[i] > rank[j]) { id[j] = id[i]; } else { id[i] = id[j]; ++rank[j]; } } public int find(int u) { return id[u] == u ? u : (id[u] = find(id[u])); } private int[] id; private int[] rank; } class Solution { public boolean equationsPossible(String[] equations) { UnionFind uf = new UnionFind(26); for (final String e : equations) if (e.charAt(1) == '=') { final int x = e.charAt(0) - 'a'; final int y = e.charAt(3) - 'a'; uf.unionByRank(x, y); } for (final String e : equations) if (e.charAt(1) == '!') { final int x = e.charAt(0) - 'a'; final int y = e.charAt(3) - 'a'; if (uf.find(x) == uf.find(y)) return false; } return true; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class UnionFind: def __init__(self, n: int): self.id = list(range(n)) def union(self, u: int, v: int) -> None: self.id[self.find(u)] = self.find(v) def find(self, u: int) -> int: if self.id[u] != u: self.id[u] = self.find(self.id[u]) return self.id[u] class Solution: def equationsPossible(self, equations: List[str]) -> bool: uf = UnionFind(26) for x, op, _, y in equations: if op == '=': uf.union(ord(x) - ord('a'), ord(y) - ord('a')) return all(uf.find(ord(x) - ord('a')) != uf.find(ord(y) - ord('a')) for x, op, _, y in equations if op == '!')