|BFS| I have a question regarding problem number 133 on LeetCode

Question

/*
// Definition for a Node.
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;
    }
};
*/

class Solution {
private:
    void BreadthFirstSearch (struct Node* node) {

        bool check[128] = { 0, };

        queue<struct Node*> buffer;
        buffer.push (node);

        while (!buffer.empty()) {

            auto current = buffer.front(); buffer.pop();

            if (check[current->val] == true) continue;
            else check[current->val] = true;

            cout << current->val << " : ";

            for (const auto& element : current->neighbors) {

                buffer.push (element);
                cout << element->val << " ";
            }
            cout << endl;
        }
        return;
    }

public:
    struct Node* cloneGraph(struct Node* node) {
        
        if (node == NULL) return NULL;

        bool check[128] = { 0, };

        queue<struct Node*> buffer, copyBuffer;
        buffer.push (node);

        struct Node* clone = new struct Node;
        if (clone == NULL) throw;

        clone->val = node->val;
        copyBuffer.push (clone);
        
        while (!buffer.empty()) {

            auto& current = buffer.front(); buffer.pop();
            auto& destination = copyBuffer.front(); copyBuffer.pop();

            if (check[current->val] == true) continue;
            else check[current->val] = true;
            
            // cout << current->val << ' ' << destination->val << ' ';
            // printf ("%p %p\n", &current, &destination);

            for (const auto& element : current->neighbors) {

                buffer.push (element);

                struct Node* newNode = new struct Node;
                if (newNode == NULL) throw;

                newNode->val = element->val;
                destination->neighbors.push_back (newNode);

                copyBuffer.push (newNode);
            }
        }

        BreadthFirstSearch (node); cout << endl;
        BreadthFirstSearch (clone); cout << endl;

        return clone;
    }
};

Problem Website

The code above is the algorithm I wrote. No matter how much I think about it, it seems like my answer is correct, but I keep getting an error saying ‘You must return a copy of all the nodes in the original graph’. I can’t figure out why this error is occurring. Please help me.

I would appreciate it if you could point out what needs to be corrected. Thank you :)

I attempted to solve the problem using the BFS algorithm. However, despite getting the intended results, I was unable to solve the problem.

Answer 1

There can be multiple edges that end at the same node, so you should not skip the iteration when a node has already been visited like you do here:

if (check[current->val] == true) continue;

You can instead store an array of pointers to all the copied nodes and reuse the same node if it has already been copied to maintain the correct references.

Node* copies[101]{}; // replace the check array with this
// ...
copyBuffer.push(copies[node->val] = clone);

// inside BFS:
for (const auto& element : current->neighbors) {
    if (copies[element->val]) {
        destination->neighbors.push_back(copies[element->val]);
        continue;
    }
    buffer.push(element);
    struct Node* newNode = new struct Node;
    newNode->val = element->val;
    destination->neighbors.push_back (newNode);
    copyBuffer.push(copies[element->val] = newNode);
}

Also, you should not take references to the elements at the front of the queue as they are removed right after.

auto current = buffer.front(); buffer.pop(); // NOT auto&
auto destination = copyBuffer.front(); copyBuffer.pop();