題目網址：https://leetcode.cn/problems/evaluate-division/

題意：給一變數 pair array equations, 和一實數 array values, 其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示 Ai / Bi = values[i]。每個 Ai 或 Bi 是一個表示單個變數的 string。

另外, 有一些以 array queries 表示的問題, 其中 queries[j] = [Cj, Dj] 表示第 j 個問題, 請根據已知條件找出 Cj / Dj = ? 的結果作為答案。

返回所有問題的答案。若存在某個無法確定的答案, 則用 -1.0 替代這個答案。若問題中出現已知條件中沒有出現的 string, 也用 -1.0 替代這個答案。

注意：輸入皆為有效的, 除法運算中不會出現除數為 0 的情況, 且不存在任何矛盾的結果。

Solution：

想法：利用 Graph + DFS, 先建立有向圖, 若 query = [a, b], 且 a -> b 沒有直接連接, 則用 DFS 去尋找是否存在中繼點 c, 使得 a -> c -> b

每個 query 都要用 visited 紀錄哪些點已經拜訪過, 否則可能會陷入死循環。
e.g. a -> c -> a -> c ...

typedef pair<string, double> psd;

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations,
                                vector<double>& values,
                                vector<vector<string>>& queries) {
        // 建立有向圖
        for (int i = 0; i < values.size(); ++i) {
            // 紀錄相鄰的點和對應的 weight => {node, weight}
            adj[equations[i][0]].emplace_back(psd{equations[i][1], values[i]});
            adj[equations[i][1]].emplace_back(psd{equations[i][0], 1.0 / values[i]});
        }

        vector<double> res;

        // 遍歷每個 query
        for (const auto& query : queries) {
            // 每個 query 中都要記錄已經拜訪過的點, 避免陷入死循環
            unordered_set<string> visited;

            // 若已知條件沒有該 node, 則答案為 -1
            if (adj.find(query[0]) == adj.end() || adj.find(query[1]) == adj.end()) {
                res.emplace_back(-1.0);
                continue;
            }

            // 否則, DFS 尋找中繼點
            res.emplace_back(dfs(query[0], query[1], visited));
        }

        return res;
    }

private:
    // 紀錄每個 node 和其直接相鄰的 node 和對應的 val
    unordered_map<string, vector<psd>> adj; // adjacent list, 紀錄 {node, weight}

    // dfs(a, b, visited) 返回 a / b
    double dfs(string& a, string& b, unordered_set<string>& visited){
        // 若起點 = 終點, 則返回 1.0（因為 a / a = 1）
        if (a == b) {
            return 1.0;
        }

        // 遍歷 a 的 neighbor
        for (const auto& [c, weight1] : adj[a]) {
            // 若已經拜訪過, 則跳過
            if (visited.find(c) != visited.end()) {
                continue;
            }

            // 將 c 加入到 visited 中
            visited.emplace(c);

            // DFS 得到 c / b
            double weight2 = dfs(c, b, visited);

            // 若存在中繼點 c 能抵達 b, 則返回 a / b = (a / c) * (c / b)
            if (weight2 != -1) {
                return weight1 * weight2;
            }
        }

        return -1.0; // 不存在中繼點 c 能抵達 b, 返回 -1
    }
};
  • time：$O(e + q \cdot e)$ ➔ e 為 equations 的長度, q 為 queries 的長度
    • $O(e)$：建立有向圖
    • $O(q \cdot e)$：遍歷 queries, 而每個 query 的遞迴深度不超過 e
  • space：$O(e)$ ➔ 遞迴深度、equations 的長度不超過 e