399. Evaluate Division

/*
 You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

 You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

 Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.


constraints:
    0 < values[i]


- example:
  input:
    equations = [["a","b"],["b","c"]]
    values    = [2.0,3.0]
    queries   = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
  output:
    [6.00000,0.50000,-1.00000,1.00000,-1.00000]
*/

/*
notes:

if the graph is stored as a map<string, string>
for each query the algorithm might go through all the names
so it's better to map all the names to number at first

building a graph:
  time:     O(#equations)
  memory:   O(#equations)

offline:
  precalcute all the possible results
  precalc time: O(#equations * #variables) - DFS for each vertex
  query time:   O(1)
  space:        O(#variables^2)

online:
  calculate each answer
  precalc time: O(#equations)
  query time:   O(#equations)
  space:        O(#equations)
*/

/*
tricky tests:
    going backwards
    same variable (A/A = ?)
    X/X where X wasn't in equations: -1.
*/

class Solution {
public:
    /*
    approach:
        store equations as a weighted oriented graph (map<string, Edge>)
        for each equations add two edges (special cases with loops)

        make a DFS for the source vertex until we reach the target one
    */

    unordered_map<string, int> var_code;
    vector<unordered_map<int, double>> g;

    double v_div_target(int v, int target, vector<bool>& visited) {
        if (visited[v]) {
            return -1.;
        }
        visited[v] = true;

        if (v == target) {
            return 1.;
        }

        for (auto [to, val] : g[v]) {
            double to_div_target = v_div_target(to, target, visited);
            if (to_div_target != -1.) {
                // v / to = val
                // to / target = to_div_target
                // -> v / target = val * to_div_target
                return val * to_div_target;
            }
        }
        return -1.;
    }

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        for (int i = 0; i < equations.size(); ++i) {
            auto& eq = equations[i];
            for (int j = 0; j < 2; ++j) {
                const string& var_name = eq[j];
                if (!var_code.count(var_name)) {
                    int var_i = var_code.size();
                    var_code[var_name] = var_i;
                }
            }

            double val = values[i];
            int code1 = var_code[eq[0]];
            int code2 = var_code[eq[1]];
            if (code1 == code2) {
                continue;
            }
            g.resize(var_code.size());
            g[code1][code2] = val;
            g[code2][code1] = 1. / val;
        }

        vector<double> res;
        vector<bool> visited(var_code.size(), false);
        for (auto& query : queries) {
            int v = (var_code.count(query[0]) ? var_code[query[0]] : -1);
            int t = (var_code.count(query[1]) ? var_code[query[1]] : -1);
            visited.assign(visited.size(), false);

            double cur_res = ((v == -1 || t == -1) ? -1. : v_div_target(v, t, visited));
            res.push_back(cur_res);
        }
        return res;
    }
};