Share my cpp solution, both recursive and iterative and support non-unique label


  • 0
    W

    iterative (BFS)

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            if(!node)
                return NULL;
            unordered_map<UndirectedGraphNode*, UndirectedGraphNode*>
                    map({{node, new UndirectedGraphNode(node->label)}});
            queue<UndirectedGraphNode*> q({node});
            while(q.size()) {
                auto cur = q.front();
                q.pop();
                for(auto neighbor : cur->neighbors) {
                    if(map.count(neighbor) == 0) {
                        map[neighbor] = new UndirectedGraphNode(neighbor->label); 
                        q.push(neighbor);
                    }
                    map[cur]->neighbors.push_back(map[neighbor]);
                }
            }
            return map[node];
        }
    

    recursive(DFS)

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(!node)
            return NULL;
        unordered_map<int, UndirectedGraphNode*> map;
        return cloneGraphHelper(node, map);
    }
    
    UndirectedGraphNode *cloneGraphHelper(UndirectedGraphNode *node, 
            unordered_map<int, UndirectedGraphNode*>& map) {
        if(map.count(node->label)) {
            return map[node->label];
        } else {
            UndirectedGraphNode* newNode = new UndirectedGraphNode(node->label);
            map[node->label] = newNode;
            for(UndirectedGraphNode* n : node->neighbors)
                newNode->neighbors.push_back(cloneGraphHelper(n, map));
            return newNode;
        }
    }

Log in to reply
 

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