Difficulty: Medium
Link: https://leetcode.com/problems/evaluate-division/

Problem

Explanation

• 其实这道题的核心思想就是图，寻找两个点在该无向图中是否是联通的。我在此解法中采用了hash表来存储，提高了搜索效率，然后是DFS（深度优先遍历查找）。
• 提交了一次wrong answer。中途遇到两个问题：
  1. 标记路径的used[i]必须要对称，即使用了used[i] = true，必须要有一个used[i] = false与之对应。（在不符合条件的情况下正常回溯查找）
  2. 在搜索完成之后，对于没有查找到结果的要将其设置为-1.0。

cpp solution

class Solution {
public:
    unordered_map<string, unordered_map<string, double>> hash;
    unordered_map<string, bool> used;

    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        int size = queries.size();
        vector<double> res(size, 0.0);
        for (int i = 0; i < equations.size(); i++) {
            auto p = equations[i];
            hash[p.first][p.second] = values[i];
            hash[p.second][p.first] = 1 / values[i];
        }
        
        for (int i = 0; i < size; i++) {
            if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end()) {
                res[i] = -1.0;
                continue;
            }
            find(1.0, res, queries[i].first, queries[i].second, i);
            if (res[i] == 0) {
                res[i] = -1.0; // 发现第二个问题后添加的代码
            }
        }
        
        return res;
    }
    
    void find(double cur, vector<double> &res, string s, string t, int i) {
        if (res[i] != 0) {
            return;
        }
        
        if (hash.find(s) == hash.end() ) {
            res[i] = -1.0;
            return;
        } else {
            if (s == t) {
                res[i] = cur;
                return;
            } else {
                auto tmp = hash[s];
                used[s] = true;
                for (auto &p : hash[s] ) {
                    if (used.find(p.first) == used.end() || used[p.first] == false) {
                        used[p.first] = true; 
                        find(cur * p.second, res, p.first, t, i);
                        used[p.first] = false;
                    }
                }
                used[s] = false; // 发现第一个问题后添加的代码
            }
        }
        
    }
};