• ``````/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
*     int label;
*     vector<UndirectedGraphNode *> neighbors;
*     UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
//1. visit each node
//2. check if it is already not visited
//3. create node and add edges to it as neighbor
//4. mark it as visited
vector<UndirectedGraphNode*> frontier;
frontier.push_back(node);
UndirectedGraphNode *newnode;
unordered_map <int , bool> visited;
if(!node){
return node;
}
while(frontier.size()){
UndirectedGraphNode *u = frontier.front();
frontier.pop_back();
if(visited.find(u->label) == visited.end()){
// create the new node as u
newnode = new UndirectedGraphNode(u->label);
// iterate all the neighbors and add edge
for(UndirectedGraphNode *neighbor : u->neighbors){
// for each neighbor create an edge
// create new for neighbor
UndirectedGraphNode *n = new UndirectedGraphNode(neighbor->label);
(newnode->neighbors).push_back(n);
frontier.push_back(neighbor);
}
visited[u->label] = true;
}
}
return newnode;
}
};
``````

Hi guys,
I m solving this problem using BFS but I'm getting wrong results. I would really appreciate if someone can point it out.

• I think you'd better not use unordered_map <int , bool> to determine weather the element is visited or not, because it may have more than one elements that have the same label.

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