Leetcode 399 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;
    }
};