Easy ...recursive solution ....with full explanations....O(n) space ..c++11


  • 4
    A
    class Solution {
    public:
        unordered_map<UndirectedGraphNode *,UndirectedGraphNode *> created;///although it takes O(n) space but it is the efficent way to search available in C++11...for C++4.8 use map...
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            if(!node)return node; //not required ..only to be in safe side
            if(created.find(node)!=created.end())return created[node]; ///if this node is already created then just return the reference of the new node created earlier
            UndirectedGraphNode * t=new UndirectedGraphNode(node->label);///otherwise create a new node and mark corresponding node in original graph created.
            created[node]=t;
            for(int i=0;i<node->neighbors.size();i++){
                t->neighbors.push_back(cloneGraph(node->neighbors[i]));//do recursively for all its neighbors...:)
            }
            return t;
            
        }
    };

  • 0
    Z

    We both use DFS copy to solve it.


  • 2
    L

    "if(created[node])" is a very bad practice. Because operator "[]" does the following two things:

    1. find the element from container.

    2. if the element doesn't exist, the method will create a new one with default constructor and insert it into container.

    So the correctness of your code is coincidence. Even it is by design, I don't recommend it.

    A c++11 code FYI.

    class Solution {
    public:
        UndirectedGraphNode *cloneGraph(const UndirectedGraphNode *node) {
    		if (!node)
    			return nullptr;
    		if (visited.find(node->label) != visited.end())
    			return visited[node->label];
    		UndirectedGraphNode * ans = new UndirectedGraphNode(node->label);
    		visited[ans->label] = ans;
    		for (const auto & next : node->neighbors) {
    			auto x = cloneGraph(next);
    			ans->neighbors.push_back(x);
    			visited[x->label] = x;
    		}
    		return ans;
        }
    private:
    	unordered_map<int, UndirectedGraphNode *> visited;
    };

  • 0
    A

    agreed ..thanks for notifying....got to know first time ....


  • 0
    J

    I don't think it matters here, if the element doesn't exist, we will insert it anyway. The default constructor for a pointer always set it to NULL, that's not coincidence.


  • -1
    G

    I think the space should be O(n^2) if you store the nodes because each nodes has O(n) neighbors. It would be better to store the labels only.


  • 0
    C

    I don't agree. Because his first argument for unordered_map is a pointer which occupies 4 bytes, while int also takes 4 bytes.


  • 0
    J

    @sen is right. Please check the ISO standard Chapter 8.5


  • 0
    L

    I of cause know the code can work here. But the writer might not know it. “So the correctness of your code is coincidence.” The correctness depends on this problem which doesn't break the hack usage. A lot of scenarios will break the usage. If the writer knows the inside of that code, as i mentioned "Even it is by design, I don't recommend it."

    Make sense?


  • 0
    J

    I don't write this way, too. I just don't know why you said it was an coincidence directly before youd said “…even it is by design”. Hope you don't mind. ;-) Just for references.


  • 0
    J

    I suggest clearing the map after each test.


  • 0
    L

    Thanks you for the reference!


  • 0
    S

    @lijinglun, visited[x->label] = x; // i think this step is not necessary


Log in to reply
 

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