[2018-10-14] [LeetCode-Week6] 39

https://leetcode.com/problems/evaluate-division/description/

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 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

建图遍历即可。
有一条边，同时建立一条权值为倒数的逆向边。
每碰到一个查询，遍历是否存在路径并累乘边权值即可。

class Solution {
public:
    map<pair<string, string>, double> Edges;
    map<string, vector<string> > Connect;
    set<string> Vis;
    bool ok;
    
    void dfs(string u, string end, double ansNow, double &ansToPush) {
        if (u == end && Connect.count(u)) {
            ansToPush = ansNow;
            ok = true;
            return;
        }
        
        Vis.insert(u);
        for (int i = 0; i < Connect[u].size(); i++) {
            string v = Connect[u][i];
            if (!Vis.count(v)) {
                pair<string, string> E = pair<string, string>(u, v);
                dfs(v, end, ansNow * Edges[E], ansToPush);
            }
        }
    }
    
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        int n = equations.size();
        for (int i = 0; i < n; i++) {
            string u = equations[i].first;
            string v = equations[i].second;
            double val = values[i];
            
            Connect[u].push_back(v);
            Connect[v].push_back(u);
            
            pair<string, string> E1 = pair<string, string>(u, v);
            pair<string, string> E2 = pair<string, string>(v, u);
            Edges[E1] = val;
            Edges[E2] = 1 / val;
        }
        
        vector<double> ans;
        int m = queries.size();
        for (int i = 0; i < m; i++) {
            Vis.clear();
            ok = false;
            
            string u = queries[i].first;
            string v = queries[i].second;
            
            double ansToPush = -1.0f;
            dfs(u, v, 1.0f, ansToPush);
            if (!ok) ansToPush = -1.0f;
            ans.push_back(ansToPush);
        }
        return ans;
    }
};