学步园

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

思路：

首先对这个图进行搜索，深度优先广度优先是任意的。每碰到一个之前未遇到的结点则创造一个相应的新结点与这个结点对照，同时新结点的所有邻居仍然和原始结点的邻居相同。

然后更新新结点的邻居信息，在之前的搜索中新旧结点的对应关系是已知的，简单的复制即可。

题解：

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == nullptr) 
            return nullptr;
        
        using UGN_t = UndirectedGraphNode;
        using pUGN_t = UGN_t*;
        
        map<pUGN_t, pUGN_t> old_new;
        set<pUGN_t> visited;
        queue<pUGN_t> to_be_visited;
        
        // traverse the node and duplicate them,
        // including the neighbors
        to_be_visited.push(node);
        while(!to_be_visited.empty())
        {
            pUGN_t visiting = to_be_visited.front();
            to_be_visited.pop();
            
            // mark it visited
            visited.insert(visiting);
            
            // duplicate the node
            old_new[visiting] = new UndirectedGraphNode(visiting->label);
            copy(begin(visiting->neighbors), end(visiting->neighbors),
                back_inserter(old_new[visiting]->neighbors));
            
            // discover new neighbors
            for(auto nbs : visiting->neighbors)
                if (visited.find(nbs) == end(visited)) // unvisited
                    to_be_visited.push(nbs);
        }
        
        // traverse the new nodes and update all neighbors
        for(auto p : old_new)
            for(auto& nbs: p.second->neighbors)
                nbs = old_new[nbs];
                
        return old_new[node];
    }
};