Description

Submission

class Solution {
    typedef pair<string, string> PSS;
    map<PSS, double> distance;
    map<string, vector<string>> graph;
    unordered_set<string> visited;

    double dfs(string a, string b) {
        if(!graph.count(a)) return -1; // "x" -> "x"
        if(a == b) return 1.0;

        if(distance.count(make_pair(a, b))) return distance[make_pair(a, b)];

        for(auto t: graph[a]) {
            if(visited.count(t)) continue;
            visited.insert(t);
            distance[make_pair(t, b)] = dfs(t, b);
            if(distance[make_pair(t, b)] == -1) continue;
            return (distance[make_pair(a, b)] = distance[make_pair(t, b)] * distance[make_pair(a, t)]);
        }
        return -1;
    }
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int n = equations.size();

        for(int i = 0; i < n; ++i) {
            distance[make_pair(equations[i][0], equations[i][1])] = values[i];
            distance[make_pair(equations[i][1], equations[i][0])] = 1.0 / values[i];
            graph[equations[i][0]].push_back(equations[i][1]);
            graph[equations[i][1]].push_back(equations[i][0]);
        }

        vector<double> rets;
        for(auto& q: queries) {
            visited.clear();
            rets.push_back(dfs(q[0], q[1]));
        }

        return rets;
    }
};

// "a" -> "b"
// "b" -> "c"
// => "a" -> "c"