Clone Graph

题目：

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

How we serialize an undirected graph:

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 #. First node is labeled as 0. Connect node 0 to both nodes 1 and 2. Second node is labeled as 1. Connect node 1 to node 2. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

分析：

像这种做deep copy的题目，一般都分为两步进行，首先克隆结点，然后克隆链接关系。具体的实现方法是个标准的bfs。

类似的题目是copy linkedList with random pointer。

解法：

class Solution {
public:
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        // write your code here
        if (node == NULL) {
            return NULL;
        }
        queue<UndirectedGraphNode* > Q;
        Q.push(node);
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode* > hash;
        while (!Q.empty() ) {
            UndirectedGraphNode* temp = Q.front();
            Q.pop();
            if (hash.find(temp) == hash.end() ) {
                hash[temp] = new UndirectedGraphNode(temp->label);
            }
            for (int i = 0; i < temp->neighbors.size(); i++) {
                UndirectedGraphNode* curr = temp->neighbors[i];
                if (hash.find(curr) == hash.end() ) {
                    hash[curr] = new UndirectedGraphNode(curr->label);
                    Q.push(curr);
                }
            }
        }
        for (auto it = hash.begin(); it != hash.end(); it++) {
            UndirectedGraphNode* oldNode = it->first;
            UndirectedGraphNode* newNode = it->second;
            for (int i = 0; i < oldNode->neighbors.size(); i++) {
                UndirectedGraphNode* temp = oldNode->neighbors[i];
                newNode->neighbors.push_back(hash[temp]);
            }
        }
        return hash[node];
    }
};