https://leetcode-cn.com/problems/evaluate-division/

---

  给出方程式 A / B = k, 其中 A 和 B 均为用字符串表示的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。

  输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

示例 1：

输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]

输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]

解释：

给定：a / b = 2.0, b / c = 3.0

问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?

返回：[6.0, 0.5, -1.0, 1.0, -1.0 ]

示例 2：

输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]

输出：[3.75000,0.40000,5.00000,0.20000]

---

  开始，刚看完题目后，直觉就是需要找到每个变量之间的关系，然后计算出各个变量的值，最后根据 queries 来求值（暴力想法）。

  比如 示例1 中，a / b = 2.0，b / c = 3.0，这样我们可以利用这个关系找到同时满足这两个等式的解。首先我们处理 a / b = 2.0，由于 a 和 b 都是第一次遇到，因此为了方便计算，设 b = 1.0，那么 a = 2.0，然后再处理 b / c = 3.0，此时 b 我们已经设置了值 1.0，因此 c = 1.0 / 3.0。

  然后我们就能愉快的计算结果了。

  但是，这种处理方法只能计算那些比较简单的 case，有些复杂的情况，如 [["a","b"],["e","f"],["b","e"]]，这种情况下，我们的 b 和 e 即要满足等式 a / b = x 也需要满足 b / e = y，这样就得综合这两个等式来求得结果，处理起来太麻烦了。因此 pass！

解法1：邻接表 + dfs

  其实我们再仔细观察，可以发现：对于 queries 中能得到结果的等式，它的除号两边的变量都能直接找到关联或能通过一些中间变量来找到关联，这样我们可以使用一种数据结构来保存这种关联，那就是 图！

  对 示例1，我们创建一张图来观察，我们使用边权来表示这两个数的商，如 a / b = 2.0 ，b / a = 1 / 2.0

  这样，我们要求图上任意两点的商，我们只需要乘上这两点之间的路径权值即可，如 a / c = a->b->c = 2.0 * 3.0

  图常用的存储结构有两种，邻接矩阵和邻接表，这里我选择使用邻接表。

  不过好久没写图算法了，邻接表的定义方式有些模糊，依靠对邻接表的回忆使用了一个 map + array 来完成邻接表的创建。

  即使用 map 作为顶点表存储所有顶点，对一个顶点，使用一个数组 array 来存储与其相连的所有边。

  因此对于 示例1，存储的邻接表就是这样的：

Map(3) {
  'a' => [ [ 'b', 2 ] ],
  'b' => [ [ 'a', 0.5 ], [ 'c', 3 ] ],
  'c' => [ [ 'b', 0.3333333333333333 ] ]
}

  创建完邻接表后，遍历 queries 数组，若这两个变量均为邻接表中的顶点，我们就对其使用深度优先遍历计算它们的路径积，否则填入 -1.0：

var calcEquation = function(equations, values, queries) {
    let map = new Map(), res = [];
    let visit = new Map();  // visit 数组标记在搜索过程中是否访问过

    const dfs = (src, dst) => {
        // 若可达，且找到了目的节点，返回 1.0 表示成功到达
        if (src === dst) {
            return 1.0;
        }

        let adjs = map.get(src);

        // 遍历 src 的所有边，若未访问过，则对其调用 dfs 获取路径积
        for (let i = 0; i < adjs.length; ++i) {
            let next = adjs[i];
            if (!visit.get(next[0])) {
                visit.set(next[0], true);

                let ret = dfs(next[0], dst);

                visit.set(next[0], false);
                // 若可达 dst，则返回当前边权与后续的边权积 ret 的乘积
                if (ret !== -1.0) {
                    return next[1] * ret;
                }
            }
        }

        // 否则，不可达，返回 -1.0
        return -1.0;
    };

    // 创建邻接表
    for (let i = 0; i < equations.length; ++i) {
        let e = equations[i], v = values[i];

        if (!map.has(e[0])) {
            map.set(e[0], []);
            visit.set(e[0], false);
        }
        if (!map.has(e[1])) {
            map.set(e[1], []);
            visit.set(e[1], false);
        }

        let adj1 = map.get(e[0]);
        let adj2 = map.get(e[1]);
        adj1.push([e[1], v]);
        adj2.push([e[0], 1 / v]);
    }

    for (let q of queries) {
        let n0 = q[0], n1 = q[1];
        if (map.has(n0) && map.has(n1)) {
            visit.set(n0, true);
            res.push(dfs(n0, n1));
            visit.set(n0, false);
        } else {
            res.push(-1.0);
        }
    }

    return res;    
};