// 133. Clone Graph #include #include #include using namespace std; // given reference of a node in a connected undirected graph. return a deep copy // (clone) of the graph. each node in the graph contains a value (int) and a // list (list[node]). class Node { public: int val; vector neighbors; Node() { val = 0; neighbors = vector(); } Node(int _val) { val = _val; neighbors = vector(); } Node(int _val, vector _neighbors) { val = _val; neighbors = _neighbors; } }; class Solution { Node *dfs(Node *curr, unordered_map &um) { vector neighbour; Node *clone = new Node(curr->val); um[curr] = clone; for (auto i : curr->neighbors) { if (um.find(i) != um.end()) neighbour.push_back(um[i]); else neighbour.push_back(dfs(i, um)); } clone->neighbors = neighbour; return clone; } public: Node *cloneGraph(Node *node) { unordered_map um; if (node == NULL) return NULL; if (!node->neighbors.size()) { Node *clone = new Node(node->val); return clone; } return dfs(node, um); } };