LeetCode 133. Clone Graph [Medium] [C++] 解題筆記

 這題簡單來說就是給你一個用 adjacent list 儲存的圖，要你用 deep copy 完整的複製一份。

詳細描述可直接參考 133. Clone Graph 。

想法:

    這邊要複製一個圖簡單來說就是遍歷整個圖(BFS or DFS)，然後逐一創建新的節點，因為用 adjacent list 儲存所以每個 Node n 的類別中會有一個 vector<Node*> neighbors 儲存與 n 相連的所有 node 的 pointer，deep copy 的話就是指不止複製 pointer 而且連 pointer 指向的內容也要跟著複製一份(只複製 pointer 本身稱為淺複製 shallow copy)。

完整程式碼:

class Solution {

public:

Node* cloneGraph(Node* node) {

if (node == nullptr) { return nullptr; }

unordered_set<Node*> visited;

unordered_map<Node*, Node*> m;

queue<Node*> q;

q.push(node);

while (!q.empty()) {

auto cur = q.front();

q.pop();

if (visited.count(cur)) { continue; }

visited.insert(cur);

if (!m.count(cur)) {

m[cur] = new Node(cur->val);

}

auto copied = m[cur];

for (auto& neighbor : cur->neighbors) {

if (!m.count(neighbor)) {

m[neighbor] = new Node(neighbor->val);

}

q.push(neighbor);

copied->neighbors.push_back(m[neighbor]);

}

}

return m[node];

}

};