## 原题

### 英文 —— 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.

### 中文 —— 除法求值

```equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
```

## 讲义

### 并查集

• Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
• Union：将两个子集合并成同一个集合。

### 操作实例

• find(a) => a, find(g) => a, find(c) => a, find(e) => d
• union(b, e)
• a/b = 1, b/g = 1, a/c = 1, d/e = 1, d/f = 1, g/e =num,  g->value* = num * e->value, ratio = num * e->value / g->value

## 代码

``````class Solution {
private:
struct Node {
double value;
Node* parent;
Node() {parent = this;};
};

Node* find_parent(Node* node) {
if (node->parent == node) return node;
return find_parent(node->parent);
}

void union_nodes(Node* n1, Node* n2, double num, unordered_map<string, Node*> m) {
Node* p1 = find_parent(n1), *p2 = find_parent(n2);
double ratio = n2->value * num / n1->value;
for (auto node : m) {
if (find_parent(node.second) == p1) {
node.second->value *= ratio;
}
}

p1->parent = p2;
}
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
// declare
unordered_map<string, Node*> m;
vector<double> results{};
// build graph
for (int i = 0; i < equations.size(); ++i) {
if (m.find(equations[i].first) == m.end() && m.find(equations[i].second) == m.end()) {
m[equations[i].first] = new Node();
m[equations[i].second] = new Node();
m[equations[i].first]->value = values[i];
m[equations[i].second]->value = 1;
m[equations[i].second]->parent = m[equations[i].first];
} else if (m.find(equations[i].first) == m.end()) {
m[equations[i].first] = new Node();
m[equations[i].first]->parent = m[equations[i].second];
m[equations[i].first]->value = m[equations[i].second]->value * values[i];
} else if (m.find(equations[i].second) == m.end()) {
m[equations[i].second] = new Node();
m[equations[i].second]->parent = m[equations[i].first];
m[equations[i].second]->value = m[equations[i].first]->value / values[i];
} else {
union_nodes(m[equations[i].first], m[equations[i].second], values[i], m);
}
}

// calculate
for (auto query : queries) {
if (m.find(query.first) != m.end() && m.find(query.second) != m.end() && find_parent(m[query.first]) == find_parent(m[query.second])) {
results.push_back(m[query.first]->value / m[query.second]->value);
} else {
results.push_back(-1.0);
}
}

return results;
}
};``````

Share:

This site uses Akismet to reduce spam. Learn how your comment data is processed.