# Leetcode 399 Solution

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

## Solution

``````struct Node
{
public:
unordered_map<string, double> neighbors;
};

class Solution {
unordered_map<string, Node*> nodes;

bool find(const string& a, const string& b, set<string>& visited, double& value)
{
if (a == b)
{
value = 1;
return true;
}

visited.insert(a);

Node* node1 = nodes[a];
for (auto neighbor : node1->neighbors)
{
if (visited.find(neighbor.first) != visited.end())
continue;

double subvalue;
if (find(neighbor.first, b, visited, subvalue))
{
value = neighbor.second * subvalue;
return true;
}
}

return false;
}

public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries)
{
for (int i = 0; i < equations.size(); i++)
{
string val1 = equations[i].first;
string val2 = equations[i].second;

double value = values[i];

if (nodes.find(val1) == nodes.end())
nodes[val1] = new Node;
if (nodes.find(val2) == nodes.end())
nodes[val2] = new Node;

nodes[val1]->neighbors[val2] = value;
if (value != 0)
nodes[val2]->neighbors[val1] = 1 / value;
}

vector<double> res;
for (auto query : queries)
{
string val1 = query.first;
string val2 = query.second;

if (nodes.find(val1) == nodes.end() || nodes.find(val2) == nodes.end())
{
res.push_back(-1);
continue;
}

set<string> visited;

double value = -1;
if (find(val1, val2, visited, value))
res.push_back(value);
else
res.push_back(-1);
}

return res;
}
};
``````