Can anybody help me to see why my DFS solution doesn't work?


  • 0
    N

    I am using the DFS to solve this problem, however, I got the wrong answer for input {0,0,0}. My output is like {0,0,0#0#0}. I cannot figure out why. Can anybody help me? Thanks a lot
    ...
    class Solution {
    public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode node) {
    unordered_set<UndirectedGraphNode
    > myset;
    return DFS(node, myset);
    }

    UndirectedGraphNode *DFS(UndirectedGraphNode* node, unordered_set<UndirectedGraphNode*>& myset)
    {
        if(!node)
           return NULL;
        UndirectedGraphNode* newNode = new UndirectedGraphNode(node->label);
        myset.insert(node);
        
        for(int i = 0; i < node->neighbors.size(); i++)
        {
            if(myset.count(node->neighbors[i]) == 0)
            {
                UndirectedGraphNode* newNeighbor = DFS(node->neighbors[i], myset);
                newNode->neighbors.push_back(newNeighbor);
            }
            else
            {
                if(node->neighbors[i] == node)
                {
                    UndirectedGraphNode* newNeighbor = new UndirectedGraphNode(node->label);
                    newNode->neighbors.push_back(newNeighbor);
                }
            }
        }
        
        return newNode;
    }
    

    ...
    };


Log in to reply
 

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