C++ 76 ms BFS solution, using a queue


  • 0
    class Solution {
    public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node==NULL) return NULL;
        queue <UndirectedGraphNode*> graphNode;
        unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> hist;
        graphNode.push(node);
        UndirectedGraphNode *root, *cur;
        root = new UndirectedGraphNode(node->label);
        hist[node]=root;
        while (!graphNode.empty()){
            cur = graphNode.front();
            graphNode.pop();
            for (int i=0;i<cur->neighbors.size();i++){
                if (hist.find(cur->neighbors[i])==hist.end()){
                    graphNode.push(cur->neighbors[i]);
                    UndirectedGraphNode* temp = new UndirectedGraphNode(cur->neighbors[i]->label);
                    hist[cur->neighbors[i]] = temp;
                }
            }
            vector<UndirectedGraphNode*> neig;
            for (int i=0;i<cur->neighbors.size();i++){
                neig.push_back(hist[cur->neighbors[i]]);
            }
            hist[cur]->neighbors = neig;    
        }
        return root;
    }
    };

Log in to reply
 

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