Problem overview
The function cloneGraph receives node, node 1 of a connected undirected graph, or nullptr when the graph is empty. The lesson provides the node type, shown in the starter code as a comment: a struct Node with an int val, a vector<Node*> neighbors and a constructor Node(int x) that sets val. The graph has n nodes, node i has the value i, and every node can be reached from node 1.
The function returns a deep copy: exactly n brand-new nodes with the same values, where each new node's neighbor list holds the new nodes of the original node's neighbors, in the same order. No node of the copy may be a node of the original graph. The function returns the copy of node 1, and returns nullptr for an empty graph.
The examples describe a graph by adjacency lists. For [[2, 4], [1, 3], [2, 4], [1, 3]] the graph is a square of four nodes, 1-2, 2-3, 3-4 and 4-1. The copy has four new nodes with the same shape. For [[]] it is a single node with no neighbors, and for [] the function gets nullptr and returns nullptr.
The lesson asks for O(V + E) time and O(V) extra space, where V is the number of nodes and E the number of edges.
Approach: one copy per node, found through a map
Copying a node is easy. The difficulty is the links. A node's neighbors link back to it, so a naive copy that follows the neighbors would go around the square forever, and a node reached by two routes would be copied twice.
The fix is a hash map from each original node to its copy. A node's copy is made the first time the search meets the node, and that is also when the node joins a queue. A node that already has a copy is never made or queued again, which stops the search from going around a cycle and guarantees one copy per node. The map also answers "what is the copy of this neighbor?" whenever a link has to be created.
The search is a BFS. Every node in the queue already has its copy, but its copy still lacks a neighbor list. When a node leaves the queue, the search walks over its neighbors in order, makes any missing copy, and appends the copy of each neighbor to the node's copy. Walking the neighbors in the original order keeps the copied lists in the same order. A recursive DFS with the same map works too, but a graph of 50,000 nodes in a long chain makes the recursion deep, which is why the lesson uses a queue.
On the square graph, the copy has four new nodes whose neighbor lists are 1: 2 4, 2: 1 3, 3: 2 4 and 4: 1 3, the original shape, and none of them is a node of the original graph. For a single node with no neighbors, the copy is a new node with the value 1 and an empty neighbor list.
Step by step
- Handle the empty graph. If
nodeisnullptr, returnnullptr. The next lines read the node's value, which needs a node. - Create the map: an
unordered_map<Node*, Node*>namedcopies. Its keys are pointers, so two different nodes are two different keys, even with equal values. - Copy the first node:
copies[node] = new Node(node->val). Thenewmakes a node that outlives the function and gives its pointer. - Create a queue,
queue<Node*> q, of the nodes whose neighbors still have to be copied. - Push
nodeonto the queue. - Loop while the queue isn't empty.
- Take the front. Read
q.front()intocurrentfirst and then callq.pop(), sincepopreturns nothing. - Loop over
current->neighborswith aNode* neighbor. Over the whole run each edge is seen twice, once from each end. - Test whether the neighbor has no copy yet:
copies.count(neighbor) == 0. - Make its copy with
new Node(neighbor->val). - Queue the neighbor, so its own neighbors get copied later.
- Link the copies: append
copies[neighbor]tocopies[current]->neighbors. This is the key line. The copy ofcurrentpoints to the copy ofneighbor, never toneighboritself. - Return
copies[node]after the loop, the copy of node 1.
The solution in C++
class Solution {
public:
Node* cloneGraph(Node* node) {
if (node == nullptr) {
return nullptr;
}
unordered_map<Node*, Node*> copies;
copies[node] = new Node(node->val);
queue<Node*> q;
q.push(node);
while (!q.empty()) {
Node* current = q.front();
q.pop();
for (Node* neighbor : current->neighbors) {
if (copies.count(neighbor) == 0) {
copies[neighbor] = new Node(neighbor->val);
q.push(neighbor);
}
copies[current]->neighbors.push_back(copies[neighbor]);
}
}
return copies[node];
}
};
The C++ details worth a closer look:
countinstead of[]for the test.copies.count(neighbor)is 1 when the key is present and 0 otherwise, and it doesn't change the map. Writingcopies[neighbor]to test would insert the key with a null pointer when it is missing, and the node would then look as if it already had a copy.newand ownership. Eachnew Node(...)allocates on the heap, so the copies stay alive after the function returns. The caller owns them. The local map holds only pointers and disappears on return without freeing anything.frontthenpop.q.front()returns a reference to the first element, andq.pop()removes it without returning it. Here the pointer is copied intocurrentbefore the pop, so using it afterwards is safe.- Pointers as map keys. The map compares and hashes the addresses of the nodes. That is what is wanted: identity, not value.
- Range-for over pointers.
Node* neighboris a copy of the pointer, not of the node, so the loop is cheap.
Complexity
Time: O(V + E). Each node is copied once and queued once. Each adjacency list is walked once, so every edge is looked at twice, once from each end. Map operations take constant time on average.
Space: O(V) extra. The map holds one entry per node, and the queue never holds more than V nodes. The new nodes and their neighbor lists are the output itself.
Edge cases and common mistakes
- The empty graph.
nullptrin,nullptrout. Without the first check,node->valwould dereference a null pointer. - A single node. The map gets one entry, the queue yields one node with no neighbors, and the function returns a new node with an empty list.
- Linking to the original. Appending
neighborinstead ofcopies[neighbor]gives a copy whose lists lead back into the original graph. The tests report any node of the copy that belongs to the original. - Copying a node twice. Without the map check, a node reached from two neighbors is copied twice and the copy has duplicate nodes. On a cycle the search wouldn't end at all.
- Marking too late. The copy is recorded when the node joins the queue, not when it leaves. Otherwise two nodes in the queue could both create a copy of the same neighbor.
- Changing the neighbor order. The copies' lists must be in the original order. Appending while walking the original list preserves it.
- Returning the wrong node. The result is the copy of the node that was passed in,
copies[node], not the last node made.
Testing
- Adjacency lists
[[2, 4], [1, 3], [2, 4], [1, 3]]give a copy with the same four lists, made of four new nodes. [[]]gives one new node with the value 1 and no neighbors.[](nullptr) givesnullptr.
