# 2307. Check for Contradictions in Equations¶

• Time: $O(n^3)$
• Space: $O(n^2)$
  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 class Solution { public: bool checkContradictions(vector>& equations, vector& values) { // Convert string to int for a better perfermance. unordered_map strToInt; for (const vector& equation : equations) { const string& u = equation[0]; const string& v = equation[1]; if (!strToInt.count(u)) strToInt[u] = strToInt.size(); if (!strToInt.count(v)) strToInt[v] = strToInt.size(); } vector>> graph(strToInt.size()); vector seen(graph.size()); for (int i = 0; i < equations.size(); ++i) { const int u = strToInt.at(equations[i][0]); const int v = strToInt.at(equations[i][1]); graph[u].emplace_back(v, values[i]); graph[v].emplace_back(u, 1 / values[i]); } for (int i = 0; i < graph.size(); ++i) if (!seen[i] && dfs(graph, i, seen, 1.0)) return true; return false; } private: bool dfs(const vector>>& graph, int u, vector& seen, double val) { if (seen[u]) return abs(val / seen[u] - 1) > 1e-5; seen[u] = val; for (const auto& [v, w] : graph[u]) if (dfs(graph, v, seen, val / w)) return true; return false; } }; 
  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 class Solution { public boolean checkContradictions(List> equations, double[] values) { // Convert string to int for a better perfermance. Map strToInt = new HashMap<>(); for (List equation : equations) { strToInt.putIfAbsent(equation.get(0), strToInt.size()); strToInt.putIfAbsent(equation.get(1), strToInt.size()); } List>[] graph = new List[strToInt.size()]; double[] seen = new double[graph.length]; for (int i = 0; i < graph.length; ++i) graph[i] = new ArrayList<>(); for (int i = 0; i < equations.size(); ++i) { final int u = strToInt.get(equations.get(i).get(0)); final int v = strToInt.get(equations.get(i).get(1)); graph[u].add(new Pair<>(v, values[i])); graph[v].add(new Pair<>(u, 1 / values[i])); } for (int i = 0; i < graph.length; ++i) if (seen[i] != 0.0 && dfs(graph, i, seen, 1.0)) return true; return false; } private boolean dfs(List>[] graph, int u, double[] seen, double val) { if (seen[u] != 0.0) return Math.abs(val / seen[u] - 1) > 1e-5; seen[u] = val; for (Pair pair : graph[u]) { final int v = pair.getKey(); final double w = pair.getValue(); if (dfs(graph, v, seen, val / w)) return true; } return false; } } 
  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 class Solution: def checkContradictions(self, equations: List[List[str]], values: List[float]) -> bool: # Convert string to int for a better perfermance. strToInt = {} for u, v in equations: strToInt.setdefault(u, len(strToInt)) strToInt.setdefault(v, len(strToInt)) graph = [[] for _ in range(len(strToInt))] seen = [0.0] * len(graph) for i, ((A, B), value) in enumerate(zip(equations, values)): u = strToInt[A] v = strToInt[B] graph[u].append((v, value)) graph[v].append((u, 1 / value)) def dfs(u: int, val: float) -> bool: if seen[u]: return abs(val / seen[u] - 1) > 1e-5 seen[u] = val return any(dfs(v, val / w) for v, w in graph[u]) for i in range(len(graph)): if not seen[i] and dfs(i, 1.0): return True return False