1
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
2
    vector<double> res(queries.size());
3

4
    // calc elem set
5
    unordered_map<string, int> smap;
6
    int index = 0;
7
    for(auto &vec: equations) {
8
        auto it = smap.find(vec[0]);
9
        if (it == smap.end()) smap[vec[0]] = index++;
10
        it = smap.find(vec[1]);
11
        if (it == smap.end()) smap[vec[1]] = index++;
12
    }
13

14
    // for(auto p: smap) cout << p.second << endl;
15

42 collapsed lines
16
    // build graph
17
    vector<vector<double>> graph(index, vector<double>(index, -1.0));
18
    for(int k = 0, size = equations.size(); k < size; k++) {
19
        int i = smap[equations[k][0]], j = smap[equations[k][1]];
20
        graph[i][j] = values[k];
21
        graph[j][i] = 1 / values[k];
22
    }
23

24
    for(int k = 0, size = queries.size(); k < size; k++) {
25
        auto it1 = smap.find(queries[k][0]);
26
        auto it2 = smap.find(queries[k][1]);
27
        if (it1 == smap.end() || it2 == smap.end()) {
28
            res[k] = -1.0;
29
            continue;
30
        }
31

32
        if (queries[k][0] == queries[k][1]) {
33
            res[k] = 1.0;
34
            continue;
35
        }
36

37
        int i = it1->second, j = it2->second;
38
        vector<bool> visited(index, false);
39
        if (dfs(graph, visited,i, j, res[k]) == false) {
40
            res[k] = -1.0;
41
        }
42
    }
43
    return res;
44
}
45

46
bool dfs(vector<vector<double>> &graph, vector<bool> &visited, int s, int e, double &res) {
47
    if (s == e) { res = 1.0; return true; }
48
    visited[s] = true;
49
    for(int i = 0;i < graph.size(); i++) {
50
        double temp;
51
        if (visited[i] == false && graph[s][i] > 0 && dfs(graph, visited, i, e, temp)) {
52
            res = temp * graph[s][i];
53
            return true;
54
        }
55
    }
56
    return false;
57
}