My ac BFS solution


  • 0
    Y
    class Solution {
        public:
            UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
                if(node == NULL)
                    return NULL;
                deque<UndirectedGraphNode*> que, newQue;
                que.push_back(node);
                UndirectedGraphNode* head = new UndirectedGraphNode(node->label);
                newQue.push_back(head);
                unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> haveVis;
                haveVis.emplace(node, head);
                while(!que.empty()) {
                    auto tmp = que.front();
                    auto newTmp = newQue.front();
                    que.pop_front(); newQue.pop_front();
                    for(auto element : tmp->neighbors) {
                        if(haveVis.find(element) == haveVis.end()) {
                            UndirectedGraphNode *pNode = new UndirectedGraphNode(element->label);
                            haveVis.emplace(element, pNode);
                            que.push_back(element);
                            newQue.push_back(pNode);
                        }
                        newTmp->neighbors.push_back(haveVis[element]);
                    }
                }
                return head;
            }
        };

Log in to reply
 

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