We treat each variable as a node in a graph, and each equation as a weighted edge. We use union-find (disjoint set) with path compression and weight tracking to maintain the ratio between variables. If we find a contradiction (i.e., two variables are already connected but the ratio does not match), we return true.

Approach

Map each variable to an integer id.
Use union-find with a parent array and a weight array, where weight[i] is the ratio between i and its parent.
For each equation, union the two variables and check for contradiction.
When uniting, if the variables are already connected, check if the ratio matches (within 1e-5).
If a contradiction is found, return true. Otherwise, return false.

Code

[{"language":"Java","code":"class Solution {\n    public boolean checkContradictions(String[][] equations, double[] values) {\n        Map<String, Integer> id = new HashMap<>();\n        int n = 0;\n        for (String[] eq : equations) {\n            if (!id.containsKey(eq[0])) id.put(eq[0], n++);\n            if (!id.containsKey(eq[1])) id.put(eq[1], n++);\n        }\n        int[] p = new int[n];\n        double[] w = new double[n];\n        for (int i = 0; i < n; i++) { p[i] = i; w[i] = 1.0; }\n        for (int i = 0; i < equations.length; i++) {\n            int x = id.get(equations[i][0]), y = id.get(equations[i][1]);\n            double v = values[i];\n            int px = find(p, w, x), py = find(p, w, y);\n            if (px == py) {\n                if (Math.abs(w[x] / w[y] - v) > 1e-5) return true;\n            } else {\n                p[px] = py;\n                w[px] = w[y] * v / w[x];\n            }\n        }\n        return false;\n    }\n    private int find(int[] p, double[] w, int x) {\n        if (p[x] != x) {\n            int orig = p[x];\n            p[x] = find(p, w, p[x]);\n            w[x] *= w[orig];\n        }\n        return p[x];\n    }\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> boolean</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> checkContradictions</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">String</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">[][] </span><span style=\"color:#E36209;--shiki-dark:#FFAB70\">equations</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">double</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">[] </span><span style=\"color:#E36209;--shiki-dark:#FFAB70\">values</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">        Map&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">String</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">Integer</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> id </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> new</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> HashMap&#x3C;>();</span></span>

Related Tags