# LeetCode Evaluate Division

LeetCode Evaluate Division

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.

DFS代码如下：

```class Solution {
private:
bool dfs(vector<vector<double>>& graph, int start, int x, int y, int target) {
graph[start][y] = graph[start][x] * graph[x][y];
graph[y][start] = 1.0 / graph[start][y];
if(y == target)return true;

int n = graph.size();
for(int i = 0; i < n; ++i){
if(graph[start][i] == 0 && graph[y][i] != 0){
if(dfs(graph, start, y, i, target))return true;
}
}
return false;
}
double helper(vector<vector<double>>& graph, int start, int target) {
if (start == target)return 1.0;
else if (graph[start][target] != 0.0)return graph[start][target];
int n = graph.size();
for (int y = 0; y < n; ++y) {
if (y == start)continue;
if (graph[start][y] != 0.0) {
if (dfs(graph, start, start, y, target))return graph[start][target];
}
}
return -1.0;
}
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
int cnt = 0, n = equations.size();
unordered_map<string, int> hash;
for (int i = 0; i < n; ++i) {
if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++;
if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++;
}
vector<vector<double>> graph(cnt, vector<double>(cnt, 0));
for (int i = 0; i < n; ++i) {
int x = hash[equations[i].first], y = hash[equations[i].second];
graph[x][x] = 1;
graph[y][y] = 1;
graph[x][y] = values[i];
graph[y][x] = 1.0 / values[i];
}
vector<double> ans;
for (int i = 0; i < queries.size(); ++i) {
if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0);
else {
int x = hash[queries[i].first], y = hash[queries[i].second];
ans.push_back(helper(graph, x, y));
}
}
return ans;
}
};
```

BFS代码如下：

```class Solution {
private:
double bfs(vector<vector<double>>& graph, int start, int target) {
if (start == target)return 1.0;
else if (graph[start][target] != 0.0)return graph[start][target];

int n = graph.size();
queue<int> q;
for(int x = 0; x < n; ++x){
if(x != start && graph[start][x] != 0)q.push(x);
}
while(!q.empty()){
int x = q.front();
if(x == target) return graph[start][target];
q.pop();
for(int y = 0; y < n; ++y){
if(graph[start][y] == 0 && graph[x][y] != 0){
graph[start][y] = graph[start][x] * graph[x][y];
graph[y][start] = 1.0 / graph[start][y];
q.push(y);
}
}
}
return -1.0;
}
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
int cnt = 0, n = equations.size();
unordered_map<string, int> hash;
for (int i = 0; i < n; ++i) {
if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++;
if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++;
}
vector<vector<double>> graph(cnt, vector<double>(cnt, 0));
for (int i = 0; i < n; ++i) {
int x = hash[equations[i].first], y = hash[equations[i].second];
graph[x][x] = 1;
graph[y][y] = 1;
graph[x][y] = values[i];
graph[y][x] = 1.0 / values[i];
}
vector<double> ans;
for (int i = 0; i < queries.size(); ++i) {
if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0);
else {
int x = hash[queries[i].first], y = hash[queries[i].second];
ans.push_back(bfs(graph, x, y));
}
}
return ans;
}
};
```