Leetcode 399 Evaluate Division Solution

Problem description could be found @https://leetcode.com/problems/evaluate-division/

Approach - The solution is a DFS to be done on Graph, where graph nodes are the divisor and dividends. Value obtained from result is the edge weight between divisor and dividend node

 The first idea in  my mind was to create adjacency matrix with assumption that there are only 1 length string but it failed as sample testcases had  strings like ab, cd. So had to go with Adjacency list solution. Following is the accepted code which ran in 3 msec

struct node{
  double weight;
  string adjacentNode;
 
  node (double wt, string dest){
      this->weight = wt;
      this->adjacentNode = dest;
  }
};

class Graph{
    private:
        map<string, list<node *> *> nodeMap;
    public:
        Graph(){
           
        }
        void addNode(string src, string des, double wt){
            node *tempNode = new node(wt, des);
           
            list<node *> *nodeList;
            if (nodeMap.count(src) == 0){
                nodeList = new list<node *>();
                nodeMap[src] = nodeList;
            }else{
               nodeList =  nodeMap.at(src);
            }
            nodeList->push_back(tempNode);
           
            // add in reverse way
            node *tempOppNode = new node(1.0/wt, src);
           
            list<node *> *revList;
            if (nodeMap.count(des) == 0){
                revList = new list<node *>();
                nodeMap[des] = revList;
               
            }else{
               revList =  nodeMap.at(des);
            }
            revList->push_back(tempOppNode);
        }
       
        bool contains(string key){
            if (nodeMap.count(key) != 0)
                return true;
            return false;
        }
       
        double dfs(string src, string dest, set<string> traversed){
            list<node *> *myList = nodeMap[src];
            if (traversed.find(src) != traversed.end())
                return -1.0;
               
            if (myList == NULL){
                return -1.0;
            }
            traversed.insert(src);
           for (list<node *>::iterator it=myList->begin();
                    it != myList->end() ; it++){
               node *listNode = *it;
               if (listNode->adjacentNode == dest){
                   traversed.erase(src);
                   return listNode->weight;
               }else{
                   double d = dfs(listNode->adjacentNode, dest, traversed);
                   if (d != -1.0){
                       traversed.erase(src);
                       return d * listNode->weight;
                   }
               }
           }
           traversed.erase(src);
           return -1;
        }
};


class Solution {
public:
 
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        Graph g ;
        for (int i=0;i<equations.size();i++)   {
            pair<string, string> val = equations[i];
            double value = values[i];
            g.addNode(val.first, val.second, value);
         
         
        }
       
        vector<double> retVal;
        for (size_t i=0;i<queries.size();i++){
            string src = queries[i].first;
            string dest = queries[i].second;
            if (src == dest){
                if (g.contains(src))
                    retVal.push_back(1.0);
                else
                    retVal.push_back(-1.0);
            }else{
                set<string> traversed;
                double d = g.dfs(src, dest, traversed);
                retVal.push_back(d);
            }
        }
        return retVal;
    }
};