Clone Graph
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.
Constraints:
- The number of nodes in the graph is in the range [1, 100].
- 1 <= Node.val <= 100
- Node.random is null or is pointing to some node in the graph.
Examples:
Input: [[2,2],[1,1],[2,0],[0,1,1,2]]
Output: [[2,2],[1,1],[2,0],[0,1,1,2]]
Explanation: The graph is a connected undirected graph with 4 nodes. The node with value 0 has a random pointer to node with value 1 and node with value 2. The node with value 1 has a random pointer to node with value 0 and node with value 2. The node with value 2 has a random pointer to node with value 0 and node with value 1.
Solutions
Depth-First Search (DFS)
The solution uses a depth-first search (DFS) approach to traverse the graph and clone each node. A map is used to keep track of the cloned nodes to avoid cloning the same node multiple times.
class Solution {
public: Node* cloneGraph(Node* node) {
if (!node) return nullptr;
unordered_map<Node*, Node*> map;
return dfs(node, map);
}
private: Node* dfs(Node* node, unordered_map<Node*, Node*>& map) {
if (map.find(node) != map.end()) return map[node];
Node* clone = new Node(node->val);
map[node] = clone;
for (Node* neighbor : node->neighbors) {
clone->neighbors.push_back(dfs(neighbor, map));
}
return clone;
}
}Follow-up:
How would you optimize the solution for a very large graph?
