Clone Graph

dfs or bfs

//dfs

class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        unordered_map<UndirectedGraphNode *,UndirectedGraphNode *> nodeMap;
        return cloneGraph(node,nodeMap);
    }

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node,unordered_map<
        UndirectedGraphNode *,UndirectedGraphNode *>& nodeMap ){

            if(!node) return NULL;

            if(nodeMap.count(node) > 0)
                return nodeMap[node];

            UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);

            nodeMap[node] = newNode;

            for(auto it = (node->neighbors).begin(); it != (node->neighbors).end(); ++it){
                (newNode->neighbors).push_back( cloneGraph(*it,nodeMap) );
            }

            return newNode;

    }

};


//bfs
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(!node) return NULL;
        UndirectedGraphNode *clnode=new UndirectedGraphNode(node->label);
        unordered_map<UndirectedGraphNode *,UndirectedGraphNode *> map;
        map[node]=clnode;
        queue<UndirectedGraphNode *> que;
        que.push(node);
        while(!que.empty()){
            UndirectedGraphNode *current=que.front();que.pop();
            for(auto it=current->neighbors.begin();it!=current->neighbors.end();it++){
                if(map.find(*it)==map.end()){
                    UndirectedGraphNode *neibor=new UndirectedGraphNode((*it)->label);
                    map[*it]=neibor;
                    map[current]->neighbors.push_back(neibor);
                    que.push(*it);
                }else{
                    map[current]->neighbors.push_back(map[*it]);
                }
               
            }
        }
        return clnode;
}