Evaluate Division - dfs graph

division_dfs.cpp

void dfs(map<string,vector<pair<string,double>>> &mp,map<string,bool> &visit,double *result,string end,string curr,double temp){
        if(curr == end){
            *result = temp;
            return;
        }
        visit[curr] = true;
        for(auto i = 0;i<mp[curr].size();i++){
            if(visit[mp[curr][i].first] == false){
                temp *= mp[curr][i].second;
                dfs(mp,visit,result,end,mp[curr][i].first,temp);
                temp /= mp[curr][i].second;
            }
        }
        visit[curr] = false;
        return;
    }
    
    vector<double> calcEquation(vector<vector<string>>& e, vector<double>& values, vector<vector<string>>& q) {
        map<string,vector<pair<string,double>>> mp;
        map<string,bool> visit;
        for(int i=0;i<e.size();i++){
            mp[e[i][0]].push_back({e[i][1],values[i]});
            mp[e[i][1]].push_back({e[i][0],1/values[i]});
            visit[e[i][0]] = false;
            visit[e[i][1]] = false;
        }
        vector<double> ans;
        double result;
        for(int i=0;i<q.size();i++){
            result = -1.0;
            if(mp.find(q[i][1])!=mp.end() && mp.find(q[i][0])!=mp.end())
                dfs(mp,visit,&result,q[i][1],q[i][0],1.0);
            ans.push_back(result);
        }
        return ans;
    }

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

For an equation of the form a/b=k, we create an edge from a to b with weight k and edge from b to a with weight 1/k. Doing for all the given equation we create a graph. Since the equation follows chain rule, a query like a/c can be divided into a/b * b/c. Thus in the graph we can to a dfs search from a to c and keep multiplying the edges in the path to obtain the answer.