clone graph

要点：

1）利用一个点去BFS所有点，放到一个VEC里；

2）对于图上的所有点，new出新点，和old点一起放到一个map里：map[old] = new；

3）对于每一个old点p，对于p点的每个邻居，把其对应的新点放到map[p]的邻居里；

code

/**
 * 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 == NULL)
        {
            return NULL;
        }

        vector<UndirectedGraphNode *> vec = findNodes(node);

        map<UndirectedGraphNode *, UndirectedGraphNode *> hash;

        for(UndirectedGraphNode *p : vec)
        {
            UndirectedGraphNode *newnode = new UndirectedGraphNode(p->label);
            hash[p] = newnode;
        }

        for(UndirectedGraphNode *p : vec)
        {
            for(UndirectedGraphNode *tmp : p->neighbors)
            {
                hash[p]->neighbors.push_back(hash[tmp]);
            }
        }

        return hash[node];
    }

    vector<UndirectedGraphNode *> findNodes(UndirectedGraphNode *head)
    {
        vector<UndirectedGraphNode *> vec;
        list<UndirectedGraphNode *> queue;
        unordered_set<UndirectedGraphNode *> hash;

        queue.push_back(head);
        hash.insert(head);

        while(!queue.empty())
        {
            UndirectedGraphNode *p = queue.front();
            queue.pop_front();
            vec.push_back(p);

            for(UndirectedGraphNode *tmp : p->neighbors)
            {
                if(hash.find(tmp) != hash.end())
                {
                    continue;
                }
                else
                {
                    hash.insert(tmp);
                    queue.push_back(tmp);
                }
            }
        }

        return vec;
    }
};