Use the copy linked list thought, got Runtime Error, but run well on my own


  • 0
    F
    UndirectedGraphNode * graph;
        queue<UndirectedGraphNode*> q;
        unordered_set<int> mark;
        //1. add node
        q.push(node);
        while (!q.empty()) {
            UndirectedGraphNode* temp = q.front();q.pop();
            if (mark.find(temp->label) == mark.end()) {
                mark.insert(temp->label);
                UndirectedGraphNode* tempNew = new UndirectedGraphNode(temp->label);
                for (int i = 0; i<temp->neighbors.size(); i++) {
                    if (temp->neighbors[i]->label != temp->label) {
                        q.push(temp->neighbors[i]);
                    }
                    
                }
                temp->neighbors.push_back(tempNew);
            }
            
        }
        //2.copy neighbors, and delete node
        graph = node->neighbors.back();
        q.push(node);
        mark.clear();
        while (!q.empty()) {
            UndirectedGraphNode* temp = q.front();q.pop();
            if (mark.find(temp->label) == mark.end()) {
                mark.insert(temp->label);
                UndirectedGraphNode* tempNew = temp->neighbors.back();
                for (int i = 0; i<temp->neighbors.size()-1; i++) {
                    if (temp->neighbors[i]->label != temp->label) {
                        q.push(temp->neighbors[i]);
                    }
                    tempNew->neighbors.push_back(temp->neighbors[i]->neighbors.back());
                }
                temp->neighbors.pop_back();
            }
        }
        
        return graph;

  • 0
    R

    check this out .. its simple.

    class Solution {
    public:
    UndirectedGraphNode *cloneGraphUtil(UndirectedGraphNode *node,std::map<int,bool> &visited, std::map<int,UndirectedGraphNode *> &buff){
        
        visited[node->label]=1;
        UndirectedGraphNode *newnode= new UndirectedGraphNode(node->label);
        buff[node->label]=newnode;
        vector<UndirectedGraphNode *>::iterator i;
        for(i=node->neighbors.begin();i<node->neighbors.end();i++)
        {
            if(!visited[(*i)->label])
            newnode->neighbors.push_back(cloneGraphUtil(*i,visited,buff));
            else
            newnode->neighbors.push_back(buff[(*i)->label]);
        }
        return newnode;
    
    }
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            if(!node)
            return NULL;
            map<int,bool> visited;
            map<int,UndirectedGraphNode *> buff;
            return cloneGraphUtil(node,visited,buff);
        }
    };

  • 0
    W

    nice. I feel the visited set is redundant, as you add an entry everytime in visited right before you add an entry to the buff map. So you can just do the lookup there instead.


Log in to reply
 

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