歡迎fork and star：Nowcoder-Repository-github
133. 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:1/ \/ \0 --- 2/ \\_/
解析
- 考察圖的基本遍歷方法，DFS/BFS
- 注意細節bug
- 運用
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> hash進行圖的映射關系存儲
// clone graph
class Solution_133 {// date 2017/12/29 10:01
// date 2017/12/29 11:04
public:UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> hash;if (!node){return node;}if (hash.find(node)!=hash.end()) //找到，關鍵字已經訪問過{hash[node] = new UndirectedGraphNode(node->label);for (auto iter: node->neighbors){hash[node]->neighbors.push_back(cloneGraph(iter)); //遞歸DFS //超時}}return hash[node];}UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) //BFS{ if (!node){return node;} unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> hash;UndirectedGraphNode* head = new UndirectedGraphNode(node->label);hash[node] = head;queue<UndirectedGraphNode*> que;que.push(node); //que.push(head); bug 花費1小時查找while (!que.empty()){UndirectedGraphNode* q = que.front();que.pop();for (auto iter: q->neighbors){if (!hash[iter]) //還沒有訪問{UndirectedGraphNode* temp = new UndirectedGraphNode(iter->label);hash[iter] = temp;que.push(iter);}hash[q]->neighbors.push_back(hash[iter]); //將一個節點的鄰接點關系記錄下來}}return hash[node];}};
題目來源
)
