Leetcode 133 Solution

This article provides solution to leetcode question 133 (clone-graph)
Categories:
Tags:
Access this page by simply typing in "lcs 133" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/clone-graph

Solution

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> m_clones;



public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == NULL)
            return NULL;



        if (m_clones.find(node) != m_clones.end())
            return m_clones[node];



        auto clonedNode = new UndirectedGraphNode(node->label);
        m_clones[node] = clonedNode;



        for (const auto neighbor : node->neighbors)
            clonedNode->neighbors.push_back(cloneGraph(neighbor));



        return clonedNode;
    }
};