---
tags: leetcode
---

# [399. Evaluate Division](https://leetcode.com/problems/evaluate-division/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

struct edge {
    string node;
    double value;
    edge(string node, double value) : node(node), value(value) {}
};

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>> &equations, vector<double> &values, vector<vector<string>> &queries) {
        unordered_map<string, vector<edge>> graph;
        for (int i = 0; i < equations.size(); ++i) {
            //graph[equations[i][0]].push_back(equations[i][0], 1.0);
            graph[equations[i][0]].push_back(edge(equations[i][1], values[i]));
            graph[equations[i][1]].push_back(edge(equations[i][0], 1 / values[i]));
        }
        
        vector<double> answer;
        for (auto &query : queries) {
            unordered_set<string> visited;
            double x = dfs(graph, visited, query[0], query[1]);
            if (x < 0) {
                answer.push_back(-1.0);
            } else {
                answer.push_back(x);
            }
        }
        
        return answer;
    }
    
private:
    double dfs(unordered_map<string, vector<edge>> &graph, unordered_set<string> &visited, string num, string dom) {
        if (graph.find(num) == graph.end() || graph.find(dom) == graph.end()) {
            return -1.0;
        }
        if (num == dom) {
            return 1.0;
        }
        
        visited.insert(num);
        for (auto &next : graph[num]) {
            if (visited.count(next.node) != 0) {
                continue;
            }
            
            double x = dfs(graph, visited, next.node, dom);
            if (x >= 0) {
                return x * next.value;
            }
        }
        return -1.0;
    }
};

## Time Complexity
$O(V+E)$
$V$ is the number of nodes in the graph.
$E$ is the number of edges in the graph.
## Space Complexity
$O(V+E)$
# Miscellane
<!--
# Test Cases

[["a","b"],["b","c"]]
[2.0,3.0]
[["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]

[["a","b"],["b","c"],["bc","cd"]]
[1.5,2.5,5.0]
[["a","c"],["c","b"],["bc","cd"],["cd","bc"]]

[["a","b"]]
[0.5]
[["a","b"],["b","a"],["a","c"],["x","y"]]

[["x1","x2"],["x2","x3"],["x1","x4"],["x2","x5"]]
[3.0,0.5,3.4,5.6]
[["x2","x4"],["x1","x5"],["x1","x3"],["x5","x5"],["x5","x1"],["x3","x4"],["x4","x3"],["x6","x6"],["x0","x0"]]

-->