LeetCode(133)Clone a Graph

タイトルは以下の通りです.
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.        1      /\     / \    0 --- 2              \              3
次のように分析されます.
本題にはアルゴリズムがないので、書くときはよく書けばいいです.基本的な考え方はこの問題「LeetCodeブラシ問題(138)Copy List with Random Pointer」と一致している.古い図のnode*と新しい図のnode*の対応関係をhashテーブルで格納します.書き終わったら、edge cases and corner casesが走ることができるかどうかを考えてみましょう.例えば、node=NULLを入力します.例えば、入力したgraphは1つのnodeしかなく、他のnodeもエッジもありません.
マイコード:

struct UndirectedGraphNode {
   int label;
   vector<UndirectedGraphNode *> neighbors;
   UndirectedGraphNode(int x) : label(x) {};
};

class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(node==NULL)
            return NULL;
        queue<UndirectedGraphNode*> cur_queue;
        unordered_map<UndirectedGraphNode*,UndirectedGraphNode * > node_map;
        UndirectedGraphNode* head_node=new UndirectedGraphNode(node->label);
        cur_queue.push(node);
        node_map[node]=head_node;
        while(!cur_queue.empty()){
            UndirectedGraphNode* cur_node=cur_queue.front();
            cur_queue.pop();
            for(int i=0;i<cur_node->neighbors.size();i++){
                UndirectedGraphNode* neighbors_node=cur_node->neighbors[i];
                if(node_map.find(neighbors_node)==node_map.end()){
                    UndirectedGraphNode* clone_neighbors_node=new UndirectedGraphNode(neighbors_node->label);
                    node_map[cur_node]->neighbors.push_back(clone_neighbors_node);
                    node_map[neighbors_node]=clone_neighbors_node;
                    cur_queue.push(neighbors_node);
                }else{
                    node_map[cur_node]->neighbors.push_back(node_map[neighbors_node]);
                }
            }
        }
        return head_node;
    }
};

update: 2014-12-10
書き直してみると、ここは書き間違えやすいことに気づきました.
エラー:cpy_current->neighbors[i] = cur;//cpy_currentは新しいgraphの現在のノードであり、vector変数neighborsは初期化時にサイズを指定していないため、ラベルを外すことができず、push_が必要です.back. 正しい:cpy_current->neighbors.push_back(cur);

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        std::queue<UndirectedGraphNode*> que;
        std::map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
        UndirectedGraphNode *org_current, *cpy_current, *cur;
        if (node == NULL) return node;
        que.push(node);
        cpy_current = new UndirectedGraphNode(node->label);
        mp[node] = cpy_current;
        while(!que.empty()) {
            org_current = que.front();
            cpy_current = mp[org_current];
            que.pop();
            for ( int i =0; i < org_current->neighbors.size(); ++i) {
                if (mp.find(org_current->neighbors[i]) == mp.end()) {
                    cur = new UndirectedGraphNode(org_current->neighbors[i]->label);
                    mp[org_current->neighbors[i]] = cur;
                    //cpy_current->neighbors[i] = cur;
                    cpy_current->neighbors.push_back(cur);
                    que.push(org_current->neighbors[i]);
                } else {
                    cpy_current->neighbors.push_back(mp[org_current->neighbors[i]]);
                }
            }
        }
        return mp[node];
    }
};