复制无向图

首先，这是个图的问题，二话不说，咱先搬出BFS和DFS两大法宝。

基本思路是：创建一个unordered_map，其中保存指向旧节点的指针到指向新节点的指针的映射，同时也用它来判断旧节点是否被遍历过。

BFS代码如下：

//
// Created by jt on 2020/9/23.
//
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return nullptr;
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
        queue<UndirectedGraphNode*> qu;
        qu.push(node);
        // BFS
        while (!qu.empty()) {
            UndirectedGraphNode* oldNode = qu.front();
            qu.pop();
            UndirectedGraphNode* newNode = mp.count(oldNode) != 0
                    ? mp[oldNode] : new UndirectedGraphNode(oldNode->label);
            mp[oldNode] = newNode;
            for (auto p : oldNode->neighbors) {
                UndirectedGraphNode* q;
                if (mp.count(p) != 0) {
                    q = mp[p];
                } else {
                    q = new UndirectedGraphNode(p->label);
                    mp[p] = q;
                    // 如果旧节点没有遍历过，加入队列
                    qu.push(p);
                }
                newNode->neighbors.push_back(q);
            }
        }
        return mp[node];
    }
};

DFS代码如下：

//
// Created by jt on 2020/9/23.
//
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return nullptr;
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
        return dfs(node, mp);
    }

    UndirectedGraphNode* dfs(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> &mp) {
        if (!node) return nullptr;
        if (mp.count(node) != 0) return mp[node];
        UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
        mp[node] = newNode;
        for (auto p : node->neighbors) {
            newNode->neighbors.push_back(dfs(p, mp));
        }
        return newNode;
    }
};