Wrong answer for the test case: Input:{-1,1#1} Output:{-1} Expected:{-1,1#1}


  • 2
    H

    I tested my code in a C++ compiler, it works fine for the test case, but OJ says that it is a wrong answer as indicated in the title. Cannot figure out why that happens.. Basically I am trying to implement dfs in an iterative way instead of recursion. Appreciate any comments.

    class Solution {
        public:
            UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
                if(!node)
                    return node;
                unordered_map<int, UndirectedGraphNode*> hm; //mapping the node labels to the cloned node pointers
                stack<UndirectedGraphNode*> s;               //iterative dfs method: storing unvisited nodes, might contain multiple pointers to the same node 
        
                s.push(node);
                while(s.size()>0){
                    UndirectedGraphNode *cur = s.top();
                    s.pop();
                    if(!hm[cur->label]){                   // have not been expanded before
                        UndirectedGraphNode *cur_clone = new UndirectedGraphNode(cur->label); 
                        hm[cur->label] = cur_clone;
                        int len = cur->neighbors.size();
                        for(int i=0;i<len;i++){
                            UndirectedGraphNode *n = cur->neighbors[i];
                            if(hm[n->label]){                                       //construct neighborhood only when both have been visited 
                                cur_clone->neighbors.push_back(hm[n->label]);
                                if(n->label!=cur_clone->label)                     // in case of self-circle
                                    hm[n->label]->neighbors.push_back(cur_clone);
                            }else{                                                 //neighbors to be visited should be pushed into the stack    
                                s.push(n);
                            }
                        }
                    }
                }
                return hm[node->label];
            }
        };

  • 0
    S

    Did you ever figure out the bug? My code fails in the same case. I think there is a problem in the evaluator.


  • 0
    L

    I have the same problem.


Log in to reply
 

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