Share my 72 ms C++ Solution , beats 93.82% of cppsubmissions!


  • 0
    R
    /**
     * Definition for undirected graph.
     * struct UndirectedGraphNode {
     *     int label;
     *     vector<UndirectedGraphNode *> neighbors;
     *     UndirectedGraphNode(int x) : label(x) {};
     * };
     */
    class Solution {
    public:
    	UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
    		unordered_map<int, bool> hasNode;
    		unordered_map<int, UndirectedGraphNode *> NodeAddress;
    		UndirectedGraphNode *sp;
    		if (node == NULL) {
    			sp = NULL;
    			return sp;
    		}
    		sp = new UndirectedGraphNode(node->label);
    		hasNode[sp->label] = true;
    		NodeAddress[sp->label] = sp;
    		clonenode(sp,node,hasNode,NodeAddress);
    		return sp;
    
    	}
    private:
    	void clonenode(UndirectedGraphNode *sp,UndirectedGraphNode *node, unordered_map<int, bool>& hasNode, unordered_map<int, UndirectedGraphNode *>& NodeAddress) {
    		int i, j;
    		for (i = 0;i < node->neighbors.size();i++) {
    			int saber = node->neighbors[i]->label;
    			if (hasNode.find(saber) != hasNode.end()) {
    				sp->neighbors.push_back(NodeAddress[saber]);
    			}
    			else {
    				UndirectedGraphNode *newnode;
    				newnode = new UndirectedGraphNode(saber);
    				hasNode[saber] = true;
    				NodeAddress[saber] = newnode;
    				sp->neighbors.push_back(newnode);
    				clonenode(newnode, node->neighbors[i], hasNode, NodeAddress);
    			}
    		}
    		return;
    	}
    };

Log in to reply
 

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