#include "leetcode.h" class Solution { public: vector calcEquation(vector> &equations, vector &values, vector> &queries) { vector ans; map mp; map> graph; for (int i = 0; i < equations.size(); i++) { string u = equations[i][0], v = equations[i][1]; mp[u + "->" + v] = values[i]; mp[v + "->" + u] = 1 / values[i]; graph[u].push_back(v); graph[v].push_back(u); } for (int i = 0; i < queries.size(); i++) { string start = queries[i][0], end = queries[i][1]; if (graph.find(start) == graph.end() || graph.find(end) == graph.end()) { ans.push_back(-1); } else { double val = 1; map visited; bool found = false; if (start == end) found = true; else dfs(start, end, mp, graph, val, visited, found); if (found == true) ans.push_back(val); else ans.push_back(-1); } } return ans; } private: void dfs(string start, string end, map &mp, map> &graph, double &val, map &visited, bool &found) { visited[start] = 1; if (found == true) return; for (auto child : graph[start]) { if (visited[child] != 1) { val *= mp[start + "->" + child]; if (end == child) { found = true; return; } dfs(child, end, mp, graph, val, visited, found); if (found == true) return; else val /= mp[start + "->" + child]; } } } }; int main() {}