荷风送香气
竹露滴清响
C++，图论题。
- 利用hash表记录字符串到整型key的映射
- 用图的边表示除的关系值，即除和被除
- 对每条查询，dfs从头跑到尾，中间乘起来就行了
只是代码写起来麻烦，思路还是简单的。
class Solution {
private:
const int MAXG = 100;
double dfs(vector<vector<double>> &g, vector<bool> &visit, int x, int y, const int max_index) {
if (x == y) return 1.0;
for (int next = 0; next < max_index; next++) {
if (g[x][next] && !visit[next]) {
visit[next] = true;
double rev = dfs(g, visit, next, y, max_index);
visit[next] =false;
if (rev != -1.0)
return g[x][next] * rev;
}
}
return -1.0;
}
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
vector<vector<double>> g(MAXG, vector<double>(MAXG));
unordered_map<string, int> str2int;
int index = 0;
for (int i = 0; i < equations.size(); i++) {
string a = equations[i][0];
string b = equations[i][1];
double c = values[i];
int x = -1, y = -1;
if (!str2int.count(a)) {
x = index++;
str2int[a] = x;
} else x = str2int[a];
if (!str2int.count(b)) {
y = index++;
str2int[b] = y;
} else y = str2int[b];
g[x][y] = c;
g[y][x] = 1.0 / c;
}
vector<double> ans;
vector<bool> visit(index, false);
for (const vector<string> &querie : queries) {
string a = querie[0];
string b = querie[1];
if (str2int.count(a) && str2int.count(b)) {
int x = str2int[a], y = str2int[b];
visit[x] = true;
ans.emplace_back(dfs(g, visit, x, y, index));
visit[x] = false;
} else ans.emplace_back(-1.0);
}
return ans;
}
};
