// Evaluate Division class Solution { unordered_map>> adj; unordered_map> val; void dfs(string u, int b, double g) { if (val.count(u)) return; val[u] = {b, g}; for (auto& x: adj[u]) dfs(x.first, b, g*x.second); } public: vector calcEquation(vector> equations, vector& values, vector> queries) { int i = 0; for (auto& x: equations) { adj[x.first].emplace_back(x.second, values[i]); adj[x.second].emplace_back(x.first, 1.0/values[i]); i++; } i = 0; for (auto& x: adj) dfs(x.first, i++, 1); vector r; for (auto& x: queries) if (! val.count(x.first) || ! val.count(x.second)) r.push_back(-1); else { auto &u = val[x.first], &v = val[x.second]; if (u.first != v.first) r.push_back(-1); else r.push_back(v.second/u.second); } return r; } };