无向图拷贝(clone-graph)

xiaoxiao2021-03-01  10

思路:

用深度优先(DFS)进行遍历用map保存新旧值的映射关系

代码:

struct UndirectedGraphNode { int label; vector<UndirectedGraphNode *> neighbors; UndirectedGraphNode(int x) : label(x) {}; }; class Solution { public: map<UndirectedGraphNode*, UndirectedGraphNode*> m; UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (!node) return NULL; return dfs(node); } UndirectedGraphNode *dfs(UndirectedGraphNode *node) { map<UndirectedGraphNode *, UndirectedGraphNode *>::iterator iter = m.find(node); if (iter != m.end()) return iter->second; UndirectedGraphNode *p = new UndirectedGraphNode(node->label); m.insert(pair<UndirectedGraphNode *, UndirectedGraphNode *>(node, p)); for (int i = 0; i < node->neighbors.size(); ++i) { p->neighbors.push_back(dfs(node->neighbors[i])); } return p; } };

 

转载请注明原文地址: https://www.6miu.com/read-4050035.html

最新回复(0)