题目描述

给定一个图，要求复制这个图。
这个图中的label唯一，即不是按照指针的地址来判断节点相等，而是通过节点的Label判断节点相等。
注意：图可能有自环(自己连接自己的边)

样例

给定一个图
返回这个图的拷贝。

算法

深度优先搜索。
对于一个节点，递归的访问他的邻居，并且复制他的邻居节点。
需要注意：如果这个节点之前被访问过，那就不访问。 记录这个节点是否被访问采用这个节点的label信息。
在递归的过程中，如果这个节点的邻居已经创建了，那么直接找到他的指针，将指针提取出来即可。
用一个map维护这个图的访问情况。

C++ 代码：

class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {

        unordered_map<int,UndirectedGraphNode*> Map;
        UndirectedGraphNode* result = dfs(node,Map);
        return result;

    }
    UndirectedGraphNode* dfs(UndirectedGraphNode* root,unordered_map<int,UndirectedGraphNode*>& Map){

        if ( root == NULL || Map.count(root->label) ) return NULL;
        UndirectedGraphNode* cur = new  UndirectedGraphNode(root->label);
        Map[cur->label] = cur;

        for(auto it = root->neighbors.begin();it!=root->neighbors.end();++it){
            if ( !Map.count((*it)->label) ){
                UndirectedGraphNode* p = dfs(*it,Map);
                cur->neighbors.push_back(p);

            }
            else{
                UndirectedGraphNode* p = Map[(*it)->label];
                cur->neighbors.push_back(p);
            }

        }
        return cur;
    }
};