Output Limit Exceeded


  • 0
    G
    /**
     * Definition for undirected graph.
     * struct UndirectedGraphNode {
     *     int label;
     *     vector<UndirectedGraphNode *> neighbors;
     *     UndirectedGraphNode(int x) : label(x) {};
     * };
     */
    
    class Solution {
    public:
        UndirectedGraphNode *BFS(UndirectedGraphNode *root, map<UndirectedGraphNode*, UndirectedGraphNode*> &visited)
        {
         //Make the copy of root and push into the queue 
         queue<UndirectedGraphNode *> q;
          q.push(root);
          
          UndirectedGraphNode* rootCopy = new UndirectedGraphNode(root->label);
          visited[root] = rootCopy;
          
         
          while(q.empty()==false)
          {
              UndirectedGraphNode* node = q.front();
              q.pop();
              
              int n = node->neighbors.size();
              //copy the neighbors 
              for(int i=0;i<n;i++)
              {
                 UndirectedGraphNode *N = node->neighbors[i];
                 if(visited.find(N) == visited.end())     //if neighbor has not yet cloned
                 {
                     UndirectedGraphNode* nodeCopy = new UndirectedGraphNode(node->label);
                     visited[node]->neighbors.push_back(nodeCopy);
                     visited[N] = nodeCopy;
                     q.push(N);
                 }
                 else   //neighbor has cloned but not yet mapped
                 {
                     visited[node]->neighbors.push_back(visited[N]);
                 }
              }
          }
          return rootCopy;
        }
        
         
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) 
        {
         if (!node) return NULL;
         map<UndirectedGraphNode*, UndirectedGraphNode*> visited;  
         return BFS(node, visited);   //use BFS to copy
        }
    
    };

  • 0
    C

    I made the same mistake.The reason is you may push one node in the queue twice.For example, to graph:0,1,2#1,2#2,when you visit node "0",you push node "1"and "2" in the queue.When you visit node "1",you push node "2" in the queue again,then you copy node "2" twice.That means you excees the memory.


  • 0
    G

    Thanks, I was making copy of same node many time.
    UndirectedGraphNode* nodeCopy = new UndirectedGraphNode(node->label);
    It should be UndirectedGraphNode* nodeCopy = new UndirectedGraphNode(N->label);
    ^^^ neighbours copy


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.