Deep copy of graph node

Question

I'm solving LeetCode problem #133:

Given a 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]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Constraints:

• The number of nodes in the graph is in the range [0, 100].
• 1 <= Node.val <= 100
• Node.val is unique for each node.
• There are no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.

This is my code:

#include <bits/stdc++.h>

using namespace std;

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

void clone (
    const Node *NODE,
    Node *node,
    vector<Node *>& nodes,
    vector<bool>& visited
) {
    if ( visited[node->val] ) return;
    else visited[node->val] = true;

    // cout << "On node : " << node->val << endl;

    Node *temp;

    for ( Node* next : NODE->neighbors ) {
        if ( !nodes[next->val] ) {
            temp = new Node(next->val);
            nodes[next->val] = temp;
        }
        temp = nodes[next->val];
        // cout << next->val << " now neighbour of " << node->val << endl;
        (node->neighbors).push_back(temp);

        clone(next, temp, nodes, visited);
    }
}

Node* cloneGraph(Node* node) {

    if ( !node ) return NULL;

    vector<Node *> nodes(101, NULL);
    vector<bool> visited(101, false);

    Node *root = new Node(node->val);

    clone(  node, root, nodes, visited );

    return root;
}

void dfs ( Node *node, vector<bool>& visited ) {
    if ( visited[node->val] ) return;

    visited[node->val] = true;
    cout << node << " (" << node->val << ") ";

    for ( Node *next : node->neighbors ) {
        dfs( next, visited );
    }
}

int main() {
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);

    node1->neighbors.push_back(node2);
    node1->neighbors.push_back(node4);

    node2->neighbors.push_back(node1);
    node2->neighbors.push_back(node3);

    node3->neighbors.push_back(node2);
    node3->neighbors.push_back(node4);

    node4->neighbors.push_back(node1);
    node4->neighbors.push_back(node3);

    Node *root = cloneGraph(node1);

    vector<bool> visited(5, false);
    dfs( root, visited );
    cout << endl;
    
    visited = vector(5, false);
    dfs( node1, visited );
    cout << endl;


    return 0;
}

Output:

0x55b6eebd4340 (1) 0x55b6eebd4370 (2) 0x55b6eebd4410 (3) 0x55b6eebd4460 (4) 
0x55b6eebd3eb0 (1) 0x55b6eebd3ee0 (2) 0x55b6eebd3f10 (3) 0x55b6eebd3f40 (4)

As per the output, the nodes seem to be cloned properly but I get this error upon submitting :

You must return a copy of all the nodes in the original graph

Answer 1

Assuming you have defined the cloneGraph as a method of the Solution class (which is what LeetCode expects), then there is still this problem:

Whenever you look at a neighbor, you register the created node in the nodes vector, but you have not done the same for the very first node (root). As a consequence when the root is encountered again, a new node is created for it, (and only now it is registered in nodes). But as this node is not the one that is referenced by root, the final return value is not the node that the algorithm registered later.

The fix is simple. Register the root node in the nodes vector:

    Node *root = new Node(node->val);
    nodes[root->val] = root;  // add this line!

    clone(node, root, nodes, visited);

    return root;