> For the complete documentation index, see [llms.txt](https://dongzeli95s-organization.gitbook.io/swe-interview-handbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dongzeli95s-organization.gitbook.io/swe-interview-handbook/algorithm/dfs/evaluate_division.md).

# Evaluate Division

````cpp
// https://leetcode.com/problems/evaluate-division

/*
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. 
Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.
Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

Ex1:
Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
note: x is undefined => -1.0

Ex2:
Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Ex3:
Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

*/

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <cassert>

using namespace std;

// M is number of quries, N is number of equations
// Time complexity: O(M*N), Space complexity: O(N)
double dfs(string curr, string dest, unordered_map<string, vector<pair<string, double>>>& graph, 
    unordered_map<string, double>& cache,
    unordered_set<string>& visited) {
    if (cache.count(curr)) {
        return cache[curr];
    }

    if (graph.count(curr) == 0) {
        return -1.0;
    }

    if (curr == dest) {
        return 1.0;
    }

    double res = -1.0;
    // If curr string doesn't exist in graph, this operation will actually insert it into graph with an empty vector
    // Be careful because we need to check if curr string exists in graph or not.
    int n = graph[curr].size();
    for (int i = 0; i < n; i++) {
        if (visited.count(graph[curr][i].first)) {
            continue;
        }

        string next = graph[curr][i].first;
        visited.insert(next);

        double val = graph[curr][i].second;
        double subVal = dfs(next, dest, graph, cache, visited);
        if (subVal != -1) {
            res = val*subVal;
            break;
        }
    }

    cache[curr] = res;
    return res;
}

vector<double> calcEquation(vector<vector<string>>& equations, 
                            vector<double>& values, 
                            vector<vector<string>>& queries) {
    vector<double> res;
    unordered_map<string, vector<pair<string, double>>> graph;
    int n = equations.size();

    for (int i = 0; i < n; i++) {
        string s1 = equations[i][0];
        string s2 = equations[i][1];
        graph[s1].push_back(make_pair(s2, values[i]));
        graph[s2].push_back(make_pair(s1, 1.0/values[i]));
    }

    unordered_map<string, double> cache;
    unordered_set<string> visited;
    for (int i = 0; i < queries.size(); i++) {
        string s1 = queries[i][0];
        string s2 = queries[i][1];
        cache.clear();
        visited.clear();
        visited.insert(s1);
        res.push_back(dfs(s1, s2, graph, cache, visited));
    }

    return res;
}

int main() {
    vector<vector<string>> equations1 = {{"a","b"},{"b","c"}};
    vector<double> values1 = {2.0,3.0};
    vector<vector<string>> quries1 = {{"a","c"},{"b","a"},{"a","e"},{"a","a"},{"x","x"}};
    vector<double> res1 = {6.00000,0.50000,-1.00000,1.00000,-1.00000};
    assert(calcEquation(equations1, values1, quries1) == res1);

    vector<vector<string>> equations2 = {{"a","b"},{"b","c"},{"bc","cd"}};
    vector<double> values2 = {1.5, 2.5, 5.0};
    vector<vector<string>> quries2 = {{"a","c"},{"c","b"},{"bc","cd"},{"cd","bc"}};
    vector<double> res2 = {3.75000,0.40000,5.00000,0.20000};
    assert(calcEquation(equations2, values2, quries2) == res2);

    vector<vector<string>> equations3 = {{"a","b"}};
    vector<double> values3 = {0.5};
    vector<vector<string>> quries3 = {{"a","b"},{"b","a"},{"a","c"},{"x","y"}};
    vector<double> res3 = {0.50000,2.00000,-1.00000,-1.00000};
    assert(calcEquation(equations3, values3, quries3) == res3);

    vector<vector<string>> equations4 = { {"x1","x2"} };
    vector<double> values4 = { 3.0 };
    vector<vector<string>> quries4 = { {"x9","x2"},{"x9","x9"} };
    vector<double> res4 = { -1.0, -1.0 };
    assert(calcEquation(equations4, values4, quries4) == res4);
    return 0;
}```
````


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dongzeli95s-organization.gitbook.io/swe-interview-handbook/algorithm/dfs/evaluate_division.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.