Clone Graph

https://leetcode.com/problems/clone-graph/description/

Clone an undirected graph. Each node in the graph contains a labeand a list of its neighbors.

Thoughts

BFS动态找出所有点，新老结点建立起映射，并对每个点把它的所有边也插进去。当遇到map中不存在的原图节点, 则创建新图对应节点放入map中。

Code

/*
 * @lc app=leetcode id=133 lang=cpp
 *
 * [133] Clone Graph
 */
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    Node* cloneGraph(Node* node) {
        unordered_map<Node*, Node*> m;
        queue<Node*> q;
        m[node] = new Node(node->val);
        q.push(node);
        while (!q.empty()) {
            const auto cur = q.front();
            q.pop();
            for (const auto nei : cur->neighbors) {
                if (!m.count(nei)) {
                    m[nei] = new Node(nei->val);
                    q.push(nei);
                }
                (m[cur]->neighbors).push_back(m[nei]);
            }
        }
        return m[node];
    }
};