这题也可以用并查集解决。
dist[i] 记录的是当前节点i和根节点root的关系 i = dist[i] * root
const int N = 100;
class Solution {
public:
unordered_map<string, int> dict;
vector<double> dist;
int p[N];
int idx = 0;
//给节点编号
int getX(string &str){
if (!dict.count(str)) dict[str] = ++ idx;
return dict[str];
}
//并查集
int find(int x){
if (p[x] != x){
int u = find(p[x]);
dist[x] *= dist[p[x]];
p[x] = u;
}
return p[x];
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
//init
dist.resize(N, 1);
for (int i = 0; i<N; i++) p[i] = i;
for (int i = 0; i<equations.size(); i++){
int a = getX(equations[i][0]), b = getX(equations[i][1]);
int pa = find(a), pb = find(b);
if (pa != pb){
dist[pa] = values[i] * dist[b] / dist[a];
p[pa] = pb;
}
}
vector<double> ans;
for (auto &qu : queries){
double ret = -1;
if (dict.count(qu[0]) && dict.count(qu[1])){
int a = getX(qu[0]), b= getX(qu[1]);
int pa = find(a), pb = find(b);
if (pa == pb)
ret = dist[a] / dist[b];
}
ans.push_back(ret);
}
return ans;
}
};