链接：
https://leetcode-cn.com/problems/clone-graph/

关键思路：
1.题目中明明确表示不会超过100个数据，所以用了一个数组
2.每个节点克隆分两步：new一个节点和克隆邻居的指针，两步都结束才算完成。
3.new节点的时候放到task列表中，克隆邻居指针的时候要到已有信息中找一下是否有这个节点。

class Solution {
public:
    // 新的节点与旧的邻居们一一对应
    struct CloneInfo {
        int success; // 是否完成克隆
        Node* newNode;  // 新的节点
    };

    Node* cloneGraph(Node* node)
    {
        if (node == nullptr) {
            return nullptr;
        }
        vector<CloneInfo> cloneInfo(101); // 克隆信息
        queue<Node*> task; // 任务表
        CloneInfo head = {
            0,
            CreateHead(node),
        };
        cloneInfo[head.newNode->val] = head;
        task.push(head.newNode);

        // 克隆整张表
        Clone(cloneInfo, task);

        return head.newNode;
    }

private:
    Node* CreateHead(Node* node)
    {
        Node* head = new Node;
        head->val = node->val;
        // 先用旧的邻居表
        head->neighbors = node->neighbors;
        return head;
    }

    void Clone(vector<CloneInfo> cloneInfo, queue<Node*>& task)
    {
        // 遍历任务表
        while (!task.empty()) {
            Node* node = task.front();

            // 克隆邻居们
            vector<Node*>& neighbor = node->neighbors;
            auto neighborSize = neighbor.size();
            for (size_t i = 0; i < neighborSize; i++) {
                if (cloneInfo[neighbor[i]->val].newNode == nullptr) {
                    Node* node = new Node;
                    node->val = neighbor[i]->val;
                    // 先用旧的邻居表
                    node->neighbors = neighbor[i]->neighbors;

                    CloneInfo info = {
                        0,
                        node,
                    };
                    cloneInfo[info.newNode->val] = info;
                    task.push(info.newNode);
                }
                node->neighbors[i] = cloneInfo[neighbor[i]->val].newNode;
            }

            cloneInfo[node->val].success = 1;
            task.pop();
        }
    }
};