Interview Classic 150 Problem P399 Evaluate Division

---

Timeline

Timeline

2025-11-04

init

Graph

---

Problem:

P399 Evaluate Division

https://leetcode.cn/problems/evaluate-division/description/?envType=study-plan-v2&envId=top-interview-150

Note for this problem: given a/b = val, then b/a = 1/val, i.e., it is not an undirected graph. For queries, consider cases where the given variables are invalid.

Adjacency list + DFS

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <stack>
#include <utility>

using std::string;
using std::vector;
using std::unordered_map;
using std::unordered_set;
using std::stack;
using std::pair;

template <class T> struct Arc {
    T val;   // Edge weight
    int vex; // Index of the node it points to
    struct Arc<T>* next;
};

template <class T, class V> struct Node {
    T val;
    struct Arc<V>* first;
};

template <class T, class V> struct AdjGraph {
    vector<Node<T, V>> vertices;
};

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations,
                                vector<double>& values,
                                vector<vector<string>>& queries)
    {
        AdjGraph<string, double> graph;
        unordered_map<string, int> umap;
        vector<Arc<double>*> arcs;
        vector<double> res;

        int i, n = equations.size();
        string dividend, divisor;

        // ===== Build Graph =====
        for (i = 0; i < n; i++) {
            dividend = equations[i][0];
            divisor = equations[i][1];

            if (!umap.count(dividend)) {
                Node<string, double> node;
                node.val = dividend;
                node.first = nullptr;
                graph.vertices.push_back(node);
                umap[dividend] = graph.vertices.size() - 1;
            }
            if (!umap.count(divisor)) {
                Node<string, double> node;
                node.val = divisor;
                node.first = nullptr;
                graph.vertices.push_back(node);
                umap[divisor] = graph.vertices.size() - 1;
            }

            // Add two edges: forward + reverse
            Arc<double>* arc1 = new Arc<double>();
            arc1->val = values[i];
            arc1->vex = umap[divisor];
            arc1->next = graph.vertices[umap[dividend]].first;
            graph.vertices[umap[dividend]].first = arc1;
            arcs.push_back(arc1);

            Arc<double>* arc2 = new Arc<double>();
            arc2->val = 1.0 / values[i];
            arc2->vex = umap[dividend];
            arc2->next = graph.vertices[umap[divisor]].first;
            graph.vertices[umap[divisor]].first = arc2;
            arcs.push_back(arc2);
        }

        // ===== Query Phase =====
        n = queries.size();
        string start, target;
        int start_idx, target_idx;
        double ans;


        for (i = 0; i < n; i++) {
            start = queries[i][0];
            target = queries[i][1];

            if (!umap.count(start) || !umap.count(target)) {
                res.push_back(-1.0);
                continue;
            }

            start_idx = umap[start];
            target_idx = umap[target];

            if (start_idx == target_idx) {
                res.push_back(1.0);
                continue;
            }
            // index, prod
            // Node index, current product

            stack<pair<int, double>> st;
            unordered_set<int> visited;

            st.push({start_idx, 1.0});

            ans = -1.0;
            // Depth-first traversal
            while (!st.empty()) {
                auto [curr, prod] = st.top();
                st.pop();

                if (curr == target_idx) {
                    ans = prod;
                    break;
                }

                if (visited.count(curr)){
                    continue;
                }

                visited.insert(curr);

                for (Arc<double>* p = graph.vertices[curr].first; p!=nullptr; p = p->next) {
                    if (!visited.count(p->vex)){
                        st.push({p->vex, prod * p->val});
                    }
                }
            }
            res.push_back(ans);
        }

        for (auto p : arcs)
            delete p;

        return res;
    }
};

unordered_map<NodeInfoType, vector<pair<NodeInfoType,ArcInfoType>>

Useunordered_map<NodeInfoType, vector<pair<NodeInfoType,ArcInfoType>>Constructing the graph this way is the simplest.

#include <unordered_map>
#include <vector>
#include <string>
#include <stack>
#include <unordered_set>
using namespace std;

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations,
                                vector<double>& values,
                                vector<vector<string>>& queries)
    {
        // ===== Build Graph =====
        unordered_map<string, vector<pair<string, double>>> graph;

        for (int i = 0; i < equations.size(); i++) {
            string a = equations[i][0];
            string b = equations[i][1];
            double val = values[i];

            graph[a].push_back({b, val});
            graph[b].push_back({a, 1.0 / val});
        }

        // ===== Query Phase =====
        vector<double> res;
        for (auto& q : queries) {
            string start = q[0], target = q[1];
            if (!graph.count(start) || !graph.count(target)) {
                res.push_back(-1.0);
                continue;
            }

            if (start == target) {
                res.push_back(1.0);
                continue;
            }

            // DFS stack: {current node, current product}
            stack<pair<string, double>> st;
            unordered_set<string> visited;

            st.push({start, 1.0});
            double ans = -1.0;

            while (!st.empty()) {
                auto [node, val] = st.top();
                st.pop();

                if (node == target) {
                    ans = val;
                    break;
                }

                if (visited.count(node))
                    continue;

                visited.insert(node);
                for (auto& [next, weight] : graph[node]) {
                    if (!visited.count(next)) {
                        st.push({next, val * weight});
                    }
                }
            }
            res.push_back(ans);
        }

        return res;
    }
};