Leetcode: Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.

Second node is labeled as 1. Connect node 1 to node 2.

Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

/ \

0 --- 2

/ \

\_/

/** 
 * Definition for undirected graph. 
 * struct UndirectedGraphNode { 
 *     int label; 
 *     vector<UndirectedGraphNode *> neighbors; 
 *     UndirectedGraphNode(int x) : label(x) {}; 
 * }; 
 */  
class Solution {  
public:  
   UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {  
        // Note: The Solution object is instantiated only once.  
        if(node == NULL)return NULL;  
  
        queue<UndirectedGraphNode*> qu;  
        qu.push(node);  
        set<UndirectedGraphNode*> st;  
        while(!qu.empty())  
        {  
            UndirectedGraphNode* curnode = qu.front();  
            qu.pop();  
            if(st.find(curnode) != st.end()) continue;  
            st.insert(curnode);  
            vector<UndirectedGraphNode *>::iterator it = curnode->neighbors.begin();  
            while(it != curnode->neighbors.end())  
            {  
                qu.push(*it);  
                it++;  
            }  
        }  
  
        map<UndirectedGraphNode*, UndirectedGraphNode*> graphmp;  
        set<UndirectedGraphNode*>::iterator sit = st.begin();  
        for(;sit!=st.end();sit++)  
        {  
            UndirectedGraphNode* tmp = new UndirectedGraphNode((*sit)->label);  
            graphmp[*sit] = tmp;  
        }  
  
        sit = st.begin();  
        for(;sit!=st.end();sit++)  
        {  
            UndirectedGraphNode* tmp = graphmp[*sit];  
            vector<UndirectedGraphNode *>::iterator vit = (*sit)->neighbors.begin();  
            while(vit != (*sit)->neighbors.end())  
            {  
                tmp->neighbors.push_back(graphmp[(*vit)]);  
                vit++;  
            }  
        }  
  
        return graphmp[node];  
    }  
};

补充：软件开发 , C++ ,