<p>You are given an array of variable pairs <code>equations</code> and an array of real numbers <code>values</code>, where <code>equations[i] = [A<sub>i</sub>, B<sub>i</sub>]</code> and <code>values[i]</code> represent the equation <code>A<sub>i</sub> / B<sub>i</sub> = values[i]</code>. Each <code>A<sub>i</sub></code> or <code>B<sub>i</sub></code> is a string that represents a single variable.</p>

<p>You are also given some <code>queries</code>, where <code>queries[j] = [C<sub>j</sub>, D<sub>j</sub>]</code> represents the <code>j<sup>th</sup></code> query where you must find the answer for <code>C<sub>j</sub> / D<sub>j</sub> = ?</code>.</p>

<p>Return <em>the answers to all queries</em>. If a single answer cannot be determined, return <code>-1.0</code>.</p>

<p><strong>Note:</strong> 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.</p>

<p><strong>Note:&nbsp;</strong>The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> equations = [[&quot;a&quot;,&quot;b&quot;],[&quot;b&quot;,&quot;c&quot;]], values = [2.0,3.0], queries = [[&quot;a&quot;,&quot;c&quot;],[&quot;b&quot;,&quot;a&quot;],[&quot;a&quot;,&quot;e&quot;],[&quot;a&quot;,&quot;a&quot;],[&quot;x&quot;,&quot;x&quot;]]
<strong>Output:</strong> [6.00000,0.50000,-1.00000,1.00000,-1.00000]
<strong>Explanation:</strong> 
Given: <em>a / b = 2.0</em>, <em>b / c = 3.0</em>
queries are: <em>a / c = ?</em>, <em>b / a = ?</em>, <em>a / e = ?</em>, <em>a / a = ?</em>, <em>x / x = ? </em>
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
note: x is undefined =&gt; -1.0</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> equations = [[&quot;a&quot;,&quot;b&quot;],[&quot;b&quot;,&quot;c&quot;],[&quot;bc&quot;,&quot;cd&quot;]], values = [1.5,2.5,5.0], queries = [[&quot;a&quot;,&quot;c&quot;],[&quot;c&quot;,&quot;b&quot;],[&quot;bc&quot;,&quot;cd&quot;],[&quot;cd&quot;,&quot;bc&quot;]]
<strong>Output:</strong> [3.75000,0.40000,5.00000,0.20000]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> equations = [[&quot;a&quot;,&quot;b&quot;]], values = [0.5], queries = [[&quot;a&quot;,&quot;b&quot;],[&quot;b&quot;,&quot;a&quot;],[&quot;a&quot;,&quot;c&quot;],[&quot;x&quot;,&quot;y&quot;]]
<strong>Output:</strong> [0.50000,2.00000,-1.00000,-1.00000]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= equations.length &lt;= 20</code></li>
	<li><code>equations[i].length == 2</code></li>
	<li><code>1 &lt;= A<sub>i</sub>.length, B<sub>i</sub>.length &lt;= 5</code></li>
	<li><code>values.length == equations.length</code></li>
	<li><code>0.0 &lt; values[i] &lt;= 20.0</code></li>
	<li><code>1 &lt;= queries.length &lt;= 20</code></li>
	<li><code>queries[i].length == 2</code></li>
	<li><code>1 &lt;= C<sub>j</sub>.length, D<sub>j</sub>.length &lt;= 5</code></li>
	<li><code>A<sub>i</sub>, B<sub>i</sub>, C<sub>j</sub>, D<sub>j</sub></code> consist of lower case English letters and digits.</li>
</ul>

/*
class UnionFind{
public:
    UnionFind(int size){

    }
private:
    vector<string> parent;
    vector<int> rank;
};

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        
    }
};
*/


// dfs
/*
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        // create graph
        unordered_map<string, unordered_map<string, double>> calcMap;
        for(int i = 0; i < equations.size(); i++){
            string dividend = equations[i][0];
            string divisor = equations[i][1];
            double value = values[i];

            // each equation indicates 2 equations
            calcMap[dividend].emplace(make_pair(divisor, value));
            //calcMap[dividend][divisor] = value;
            calcMap[divisor].emplace(make_pair(dividend, 1.0 / value));
            //calcMap[divisor][dividend] = 1.0 / value;            
        }

        vector<double> retVal(queries.size());
        // iterate through all queries
        for(int i = 0; i < queries.size(); i++){
            string dividend = queries[i][0];
            string divisor = queries[i][1];
            // if at least one of dividend or divisor is unknown
            if(calcMap.find(dividend) == calcMap.end() || calcMap.find(divisor) == calcMap.end())
                retVal[i] = -1;
            // both dividend and divisor are known and the same
            else if(dividend == divisor)
                retVal[i] = 1;
            // both dividend and divisor are known and different
            else{
                // avoid infinite loop
                unordered_set<string> visited;
                // default answer to -1 in case no possible solution can be found => both dividend and divisor are known but in different componenets
                double ans = -1;
                // dfs until we found divisor. propagate the cumulative product all the way
                dfs(calcMap, visited, dividend, divisor, ans, 1.0);
                retVal[i] = ans;
            }
        }
        return retVal;
    }

    void dfs(unordered_map<string, unordered_map<string, double>>& calcMap, unordered_set<string>& visited, string dividend, string& divisor, double& ans, double product){
        visited.insert(dividend);
        // all results with dividend == dividend
        auto results = calcMap[dividend];
        if(results.find(divisor) != results.end()){
            ans = product * results[divisor];
            return;
        }

        for(auto newPair : results){
            if(visited.find(newPair.first) == visited.end()){
                // call dfs with new dividend but the same divisor, propagate the cumulative product all the way
                dfs(calcMap, visited, newPair.first, divisor, ans, product * newPair.second);
            }
        }
    }
};
*/


// Modified UnionFind data structure.
class Relation {
 public:
  explicit Relation(int size) : base_(size), ranks_(size) {
    for (int i = 0; i < size; ++i) {
      base_[i] = {i, 1.0};
    }
  }

  // Find(x) returns [x0, ratio] such that $x = ratio * $x0.
  pair<int, double> Find(int x) {
    pair<int, double>& base = base_[x];
    if (base.first != x) {
      auto [x0, ratio] = Find(base.first);
      base.first = x0;
      base.second *= ratio;
    }
    return base;
  }

  void Add(int x, double ratio, int y) {
    auto [x0, ratio_x] = Find(x);
    auto [y0, ratio_y] = Find(y);
    if (x0 == y0) {
      return;  // We must have ratio_x = ratio_y * ratio in this case.
    }
    if (ranks_[x0] < ranks_[y0]) {
      // Now we have ratio_x * x0 = ratio * ratio_y * y0
      // => x0 = ratio * ratio_y / ratio_x y0
      base_[x0] = {y0, ratio * ratio_y / ratio_x};
    } else if (ranks_[x0] > ranks_[y0]) {
      base_[y0] = {x0, ratio_x / ratio_y / ratio};
    } else { // same rank
      ++ranks_[y0];
      base_[x0] = {y0, ratio * ratio_y / ratio_x};
    }
  }

 private:
  vector<pair<int, double>> base_;
  vector<int> ranks_;
};

class IdGen {
 public:
  // The argument `string_view` must not point to temporary strings.
  int GetId(string_view v) {
    int& id = lookup_[v];
    if (id == 0) {
      id = ++id_counter_;
    }
    return id;
  }

  int max() const { return id_counter_; }

 private:
  int id_counter_ = 0;
  unordered_map<string_view, int> lookup_;
};

class Solution {
public:
  vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values,
                              vector<vector<string>>& queries) {
    IdGen id_gen;
    Relation relation(equations.size() * 2 + 1);
    for (int i = 0; i < equations.size(); ++i) {
      const vector<string>& equation = equations[i];
      int a = id_gen.GetId(equation[0]);
      int b = id_gen.GetId(equation[1]);
      relation.Add(a, values[i], b);  // $a == values[i] * $b
    }
    const int max_id = id_gen.max();

    vector<double> results(queries.size(), -1.0);
    for (int i = 0; i < queries.size(); ++i) {
      const vector<string>& query = queries[i];
      int c = id_gen.GetId(query[0]);
      if (c > max_id) {
        continue;
      }
      int d = id_gen.GetId(query[1]);
      if (d > max_id) {
        continue;
      }
      // $c = ratio_c * $c0
      auto [c0, ratio_c] = relation.Find(c);
      // $d = ratio_d * $d0
      auto [d0, ratio_d] = relation.Find(d);
      if (c0 != d0) {
        continue;
      }
      // Therefore we get $c / $d.
      results[i] = ratio_c / ratio_d;
    }
    return results;
  }
};

10600