> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/exhaustive-search/yun-suan/evaluate-division.md).

# Evaluate Division

https\://leetcode.com/problems/evaluate-division/description/

> Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
>
> Example:
>
> Given a / b = 2.0, b / c = 3.0.
>
> queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
>
> return \[6.0, 0.5, -1.0, 1.0, -1.0 ].
>
> The input is: vector\<pair\<string, string>> equations, vector\<double>& values, vector\<pair\<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector\<double>.
>
> According to the example above:
>
> equations = \[ \["a", "b"], \["b", "c"] ],
>
> values = \[2.0, 3.0],
>
> queries = \[ \["a", "c"], \["b", "a"], \["a", "e"], \["a", "a"], \["x", "x"] ].
>
> The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

## Thoughts

给一系列变量之间相除的结果，返回给定两个变量之间相除的结果。根据例子写一下就知道比如求a/c, 需要a/b \* b/c, 要先找到a/b, 再找到b/c 因此是道搜索题。\
别忘了divisor/dividend = 1/（dividend/divisor）也加入已知eqs中。

## Code

```cpp
/*
 * @lc app=leetcode id=399 lang=cpp
 *
 * [399] Evaluate Division
 */
class Solution {
private:
    double dfs(const string &a, const string &t, unordered_map<string, unordered_map<string, double>> &m, unordered_set<string> &visited) {
        if (!m.count(a) || !m.count(t)) return -1;
        if (a == t) return 1;
        visited.insert(a);
        for (const auto &p : m[a]) {
            const string &b = p.first;
            if (!visited.count(b)) {
                const auto r = dfs(b, t, m, visited);
                if (r != -1) return r * m[a][b];
            }
        }
        return -1;
    }
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, unordered_map<string, double>> m;
        for (int i = 0; i < equations.size(); ++i) {
            const auto &eq = equations[i];
            m[eq[0]][eq[1]] = values[i];
            m[eq[1]][eq[0]] = 1 / values[i]; 
        } 
        const int N = queries.size();
        vector<double> res(N);
        unordered_set<string> visited;
        for (int i = 0; i < N; ++i) {
            res[i] = dfs(queries[i][0], queries[i][1], m, visited);
            visited.clear();
        }
        return res;
    }
};


```

## Analysis

Errors:\
1\. dfs在判断结果是否-1前就乘了

query的每次时间复杂度O(N), N为equations数目.