133. Clone Graph

Clone an undirected graph. Each node in the graph contains alabeland a list of itsneighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use#as a separator for each node, and,as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph{0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by#.

1. First node is labeled as 0. Connect node 0to both nodes 1and 2.

2. Second node is labeled as 1. Connect node 1to node 2.

3. Third node is labeled as 2. Connect node 2to node 2(itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Thoughts:

1. BFS/DFS + node mapping

Code (BFS)

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
    // mp maps original node to the copy node
    unordered_map <UndirectedGraphNode*, UndirectedGraphNode*> mp;

public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(!node) return node;
        queue<UndirectedGraphNode* > q;
        UndirectedGraphNode* head = new UndirectedGraphNode(node->label);
        mp[node] = head;
        q.push(node);
        while(!q.empty()){
            // do two things: 1. update mapping record for NEIGH node 2. copy neighbor for the current node 
            UndirectedGraphNode * cur = q.front(); q.pop();
            for(auto neigh : cur->neighbors){
                if(mp.find(neigh) == mp.end()){
                    UndirectedGraphNode* cp_node = new UndirectedGraphNode(neigh->label);
                    mp[neigh] = cp_node;
                    q.push(neigh);
                }
                // copy cur neighbors
                mp[cur] -> neighbors.push_back(mp[neigh]);
            }
        }

        return head;
    }

};

Code (DFS)

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
    unordered_map <UndirectedGraphNode*, UndirectedGraphNode*> mp;
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(!node) return node;
        if(mp.find(node) == mp.end()){
            UndirectedGraphNode * head = new UndirectedGraphNode(node->label);
            mp[node] = head;
            for(auto neigh: node->neighbors){
            mp[node]-> neighbors.push_back(cloneGraph(neigh));

            }
        }

        return mp[node];
    }

};

Special Thanks jianchaolifighter's solution