Accepted recursive depth first search solution


  • 19
    N
    class Solution {
    public:
    	UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) 
    	{
    		// initialize marks
    		map<int, UndirectedGraphNode*> marks;
    		if (node) return dfs(node, marks);
    		else return NULL;
    	}
    
    	UndirectedGraphNode * dfs(UndirectedGraphNode *node, map<int, UndirectedGraphNode*> & marks)
    	{
    		// create new node and search its all neighbors
    		UndirectedGraphNode *p;
    		p = new UndirectedGraphNode(node->label);
    		marks[p->label] = p;
    
    		// loop all neighbors
    		for(UndirectedGraphNode* n : node->neighbors)
    		{
    			// hook already created and searched node
    			if(marks.count(n->label) > 0)
    				(p->neighbors).push_back(marks[n->label]);
    			else
    				(p->neighbors).push_back(dfs(n,marks));
    		}
    		return p;
    	}
    };

  • 0
    B
    This post is deleted!

  • 0
    M

    who can tell me the difference between the following statements:

    1. (p->neighbors).push_back(marks[n->label]);
    2. (p->neighbors).push_back(n);
      why the second is wrong ?

  • 0
    M

    I figure it out : marks[n->label] is the copy of n, they are not the same address.


Log in to reply
 

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