Problem#
給你一個 string 陣列 equations 和 double 陣列 value，其中 equations[i] = {A_i, B_i} 和 values[i] 代表 A_i / B_i = values[i]
接著給你 query 陣列，其中 query[j] = {C_j, D_j} 代表要查詢 C_j / D_j 是多少
回傳所有的答案，如果答案找不到則回傳 -1.0 即可
- 測資限制:
- $1 \le \text{len(equations)} = \text{len(values)} \le 20$
- $0.0 \le values[i] \le 20.0$
- $1 \le \text{len(queries)} \le 20$
想法#
從例題一 $\frac{a}{b} = 2.0$, $\frac{b}{c} = 3.0$ 問 $\frac{a}{c}$ 是多少，則可以得出 $\frac{a}{b} * \frac{b}{c} = \frac{a}{c} = 2.0 * 3.0 = 6.0$
如果將 $\frac{a}{b}$ 看成是有 a 和 b 兩個點，而 $\frac{a}{b}$ 就是 a->b 的邊上的權重的話，則這題問題就可以轉化成：是否存在一條路徑能從 a 到 c？
而 $\frac{a}{c}$ 則變成了這條路徑(a->b->c)的邊的權重相乘而得，要知道圖的兩點是否存在一條路徑，最簡單就是去 dfs or bfs
- 時間複雜度: $\mathcal{O}(QE)$
- 空間複雜度: $\mathcal{O}(E)$
- $E = \text{equations}, Q = \text{query}$
AC Code#
賞析#
TODO
心得#
這題解法簡單，但要想到能把題目轉化成圖有點難