/**
* 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
}
};
Output Limit Exceeded


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.