399-2

class Solution {
public:
    map<string, int> m;
    double result;
    void dfs(int source, int dest, vector<vector<pair<int, double>>> &graph, vector<bool> &vis, double res){
        if(source == dest) result = res;
        vis[source] = true;
        for(auto child: graph[source]){
            if(!vis[child.first]){
                dfs(child.first, dest, graph, vis, res*child.second);
            }
        }
        vis[source] = false;
    }

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        vector<vector<pair<int, double>>> graph(40);
        int count = 0;

        // Make the graph.
        for(int i=0; i<equations.size(); i++){
            auto &edge = equations[i];
            if(!m.count(edge[0]))
                m[edge[0]] = count++;
            if(!m.count(edge[1]))
                m[edge[1]] = count++;
            int from = m[edge[0]], to = m[edge[1]];
            double val = values[i];
            graph[from].push_back({to, val});
            graph[to].push_back({from, 1.0/val});
        }

        // Making self loops.
        for(int i=0; i<count; i++)
            graph[i].push_back({i, 1.0});

        // For each query do dfs from source to destination.
        vector<double> ans;
        vector<bool> vis(count, false);
        for(auto q: queries){
            if(m.count(q[0]) && m.count(q[1])){
                int x = m[q[0]];
                int y = m[q[1]];
                result = -1.0;
                dfs(x, y, graph, vis, 1.0);
                ans.push_back(result);
            }
            else
                ans.push_back(-1.0);
        }
        return ans;
    }
};