C++ . Wrong answer. Please help.


  • 0
    H
    /**
     * Definition for undirected graph.
     * struct UndirectedGraphNode {
     *     int label;
     *     vector<UndirectedGraphNode *> neighbors;
     *     UndirectedGraphNode(int x) : label(x) {};
     * };
     */
    class Solution {
    public:
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            //1. visit each node 
            //2. check if it is already not visited
            //3. create node and add edges to it as neighbor
            //4. mark it as visited
            vector<UndirectedGraphNode*> frontier;
            frontier.push_back(node);
            UndirectedGraphNode *newnode;
            unordered_map <int , bool> visited;
            if(!node){
                return node;
            }
            while(frontier.size()){
                UndirectedGraphNode *u = frontier.front();
                frontier.pop_back();
                if(visited.find(u->label) == visited.end()){
                    // create the new node as u
                    newnode = new UndirectedGraphNode(u->label);
                    // iterate all the neighbors and add edge
                    for(UndirectedGraphNode *neighbor : u->neighbors){
                        // for each neighbor create an edge
                        // create new for neighbor
                        UndirectedGraphNode *n = new UndirectedGraphNode(neighbor->label);
                        (newnode->neighbors).push_back(n);
                        frontier.push_back(neighbor);
                    }
                    visited[u->label] = true;
                }
            }
            return newnode;
        }
    };
    

    Hi guys,
    I m solving this problem using BFS but I'm getting wrong results. I would really appreciate if someone can point it out.


  • 0
    Y

    I think you'd better not use unordered_map <int , bool> to determine weather the element is visited or not, because it may have more than one elements that have the same label.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.