Clone Graph

• Time : $O(v + e)$
• Space : $O(v)$

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
void dfs(UndirectedGraphNode* node, unordered_map<int, UndirectedGraphNode*>& copy) {
    copy[node->label] = new UndirectedGraphNode(node->label);
    for(auto v : node->neighbors) {
        if(copy.count(v->label)) continue;
        dfs(v, copy);
    }
}
void dfs2(UndirectedGraphNode* node, unordered_map<int, UndirectedGraphNode*>& copy, unordered_set<int>& vis) {
    vis.insert(node->label);
    for(auto v : node->neighbors) {
        copy[node->label]->neighbors.push_back(copy[v->label]);
        if(!vis.count(v->label)) dfs2(v, copy, vis);
    }
}
UndirectedGraphNode *Solution::cloneGraph(UndirectedGraphNode *node) {
    unordered_map<int, UndirectedGraphNode*> copy;
    dfs(node, copy);
    dfs2(node, copy, unordered_set<int>() = {});
    return copy[node->label];
}