399. Evaluate Division

Version #2 DFS[TODO]


Version #1 Union Find
一开始写的时候感觉我靠怎么这么难，但是实际上用recursion的方法进行path compression 就非常容易
如果root() 用iteration的方法，每次指向grandpa, 路径缩短一半，没有办法保证最后的 ratio.get(a) 就是 rootA / a
这是这道题的关键
如果一开始就用 recursion的方法 取出root(father.get(a))
然后由  rootA / father = ratio.get(father) + father / id = ratio.get(id)
得到 rootA / id = ratio.get(father) * ratio.get(id)
就可以把id直接连在root上
这样保证了一切换算都是从root出发的
只要root一样，a / b 就一定是 a / b = root / b / (root / a) = ratio.get(b) / ratio.get(a)
不需要处理任何edge case，就很牛逼了

Input:[["a","b"],["e","f"],["b","e"]] [3.4,1.4,2.3] [["b","a"],["a","f"],["f","f"],["e","e"],["c","c"],["a","c"],["f","e"]]

Output:[0.29412,0.17903,1.0,1.0,-1.0,-1.0,43.68029]

Expected:[0.29412,10.948,1.0,1.0,-1.0,-1.0,0.71429]

75.23 %
class Solution {
    private Map<String, String> father;
// id, fatherValue/value
private Map<String, Double> ratio;

public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
//   2.0
// a ---> b
father = new HashMap<>();
ratio = new HashMap<>();
for (int i = 0; i < equations.length; i++) {
String a = equations[i][0];
String b = equations[i][1];
union(a, b, values[i]);
}
double[] result = new double[queries.length];
for (int i = 0; i < queries.length; i++) {
String a = queries[i][0];
String b = queries[i][1];
if (!father.containsKey(a) || !father.containsKey(b)) {
result[i] = -1.0;
continue;
}
String rootA = root(a);
String rootB = root(b);
if (!rootA.equals(rootB)) {
result[i] = -1.0;
} else {
// a / b = rootA / a
result[i] = ratio.get(b) / ratio.get(a);
}
}
return result;
}

// path compression needs to recalculate the ratio
// father
private String root(String id) {
if (!father.containsKey(id)) {
father.put(id, id);
ratio.put(id, 1.0);
}
if (father.get(id).equals(id)) {
            return id;
        }
        String parent = father.get(id);
        String root = root(parent);
        // ratio.get(parent) = root / parent, ratio.get(id) = parent / id
        // root / id = ratio.get(parent) * ratio.get(id)
        father.put(id, root);
        ratio.put(id, ratio.get(parent) * ratio.get(id));
return root;
}

// a / b = 2.0, b / c = 3.0.
// a / c = (a/b) * (b/c) = 6
private void union(String a, String b, Double weight) {
            String rootA = root(a);
            String rootB = root(b);
            double ratioA = ratio.get(a);
            double ratioB = ratio.get(b);
            if (rootA.equals(rootB)) {
                return;
            }
            // a / b = weight
            // rootA  = ratioA * a
            // rootB  = ratioB * b
            // rootA / rootB = ratioA * a / (ratioB * b) = ratioA / ratioB * (a / b) = ratioA / ratioB * weight
            father.put(rootB, rootA);
            ratio.put(rootB, ratioA / ratioB * weight);
}
}