algorithmbreadth-first-searchbrute-force

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


/*
// 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.


Solution

  • 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();