# Share my 0 ms solution, use union find

• if we have b = k0 * a and c = k1*b, we set a as parent of b and b as parent of c, we also need to record the ratio. In this way, we can trace everything back to the original variable.

``````class Solution {
unordered_map<string, double> vmap;
unordered_map<string, string> rmap;
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
for(int i = 0; i < equations.size(); i ++)
{
pair<string, string>& p = equations[i];
rmap[p.first] = p.first;
rmap[p.second] = p.second;
vmap[p.first] = vmap[p.second] = 1.0;
}
for(int i = 0; i < equations.size(); i ++)
{
pair<string, string>& p = equations[i];

string s = p.first;
string t = p.second;

//s = k * t

double ks = 1.0;
while(rmap[s] != s)
{
ks *= vmap[s];
s = rmap[s];
}

double ts = 1.0;
while(rmap[t] != t)
{
ts *= vmap[t];
t = rmap[t];
}

if(s == t)
continue;

double k = values[i] * ts / ks;
if(s < t)
{
swap(s, t);
k = 1 / k;
}
vmap[s] = k;
rmap[s] = t;
}

vector<double> vret;
for(int i = 0; i < queries.size(); i ++)
{
pair<string, string>& p = queries[i];
string s = p.first;
string t = p.second;

if(rmap.find(s) == rmap.end() || rmap.find(t) == rmap.end())
{
vret.push_back(-1);
continue;
}

double ks = 1.0;
while(rmap[s] != s)
{
ks *= vmap[s];
s = rmap[s];
}

double ts = 1.0;
while(rmap[t] != t)
{
ts *= vmap[t];
t = rmap[t];
}

if(s != t)
vret.push_back(-1);
else
vret.push_back(ks / ts);
}

return vret;

}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.