Sharing my 96ms C++ solution


  • 0
    T
    /**
     * Definition for undirected graph.
     * struct UndirectedGraphNode {
     *     int label;
     *     vector<UndirectedGraphNode *> neighbors;
     *     UndirectedGraphNode(int x) : label(x) {};
     * };
     */
     
    class Solution {
    private:
        void representation(UndirectedGraphNode* node, unordered_map<UndirectedGraphNode*, vector<UndirectedGraphNode*>> &myGraph)
        {
            if(myGraph.count(node)>0)
                return;
                
            vector<UndirectedGraphNode*> v = node->neighbors;
            myGraph[node] = v;
            for(int i=0; i<v.size(); i++)
                representation(v[i], myGraph);
        }
        
    public:
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            if(node==NULL)
                return NULL;
                
            UndirectedGraphNode* result;
            unordered_map<UndirectedGraphNode*, vector<UndirectedGraphNode*>> myGraph;
            representation(node, myGraph);
            
            unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> myMap;
            for(auto x=myGraph.begin(); x!=myGraph.end(); x++)
            {
                myMap[x->first] = new UndirectedGraphNode(x->first->label);
                if(x->first==node)
                    result = myMap[x->first];
            }
            
            for(auto y=myGraph.begin(); y!=myGraph.end(); y++)
            {
                vector<UndirectedGraphNode*> v = y->second;
                UndirectedGraphNode* tmp = y->first;
                for(int i=0; i<v.size(); i++)
                    (myMap[tmp]->neighbors).push_back(myMap[v[i]]);
            }
            
            return result;
        }
    };

Log in to reply
 

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