Title
Evaluate Division
Question description
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.
Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.
Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?这道题本质上是“带权图上的路径乘积查询”。把每个变量看成图中的节点，把方程 Ai / Bi = value 视为从 Ai 到 Bi 的有向边权重为 value，同时反向边权重为 1/value。对于每个查询 Cj / Dj，只要在图中找到一条从 Cj 到 Dj 的路径，就把路径上的权重连乘得到答案；如果两点不连通，或者变量根本没出现过，就返回 -1.0。常见做法是用 DFS/BFS 搜索路径，或者用并查集维护连通关系与相对比值，适合面试中考察图建模与查询处理能力。
