aboutsummaryrefslogtreecommitdiff
path: root/evaluate_division.cpp
blob: 7bda6274c299a4b26028c079710367cb809d2cde (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include "leetcode.h"

class Solution {
public:
  vector<double> calcEquation(vector<vector<string>> &equations,
                              vector<double> &values,
                              vector<vector<string>> &queries) {
    vector<double> ans;
    map<string, double> mp;
    map<string, vector<string>> graph;
    for (int i = 0; i < equations.size(); i++) {
      string u = equations[i][0], v = equations[i][1];
      mp[u + "->" + v] = values[i];
      mp[v + "->" + u] = 1 / values[i];
      graph[u].push_back(v);
      graph[v].push_back(u);
    }
    for (int i = 0; i < queries.size(); i++) {
      string start = queries[i][0], end = queries[i][1];
      if (graph.find(start) == graph.end() || graph.find(end) == graph.end()) {
        ans.push_back(-1);
      } else {
        double val = 1;
        map<string, int> visited;
        bool found = false;
        if (start == end)
          found = true;
        else
          dfs(start, end, mp, graph, val, visited, found);
        if (found == true)
          ans.push_back(val);
        else
          ans.push_back(-1);
      }
    }
    return ans;
  }

private:
  void dfs(string start, string end, map<string, double> &mp,
           map<string, vector<string>> &graph, double &val,
           map<string, int> &visited, bool &found) {
    visited[start] = 1;
    if (found == true)
      return;
    for (auto child : graph[start]) {
      if (visited[child] != 1) {
        val *= mp[start + "->" + child];
        if (end == child) {
          found = true;
          return;
        }
        dfs(child, end, mp, graph, val, visited, found);
        if (found == true)
          return;
        else
          val /= mp[start + "->" + child];
      }
    }
  }
};

int main() {}