获取网站开发语言,北京做网站最好的公司,服装网站建设中期目标,外贸网站建设青岛1. 题目
给定无向连通图中一个节点的引用#xff0c;返回该图的深拷贝#xff08;克隆#xff09;。图中的每个节点都包含它的值 val#xff08;Int#xff09; 和其邻居的列表#xff08;list[Node]#xff09;。
class Node {
public:int val;vectorNode* n…1. 题目
给定无向连通图中一个节点的引用返回该图的深拷贝克隆。图中的每个节点都包含它的值 valInt 和其邻居的列表list[Node]。
class Node {
public:int val;vectorNode* neighbors;Node() {}Node(int _val, vectorNode* _neighbors) {val _val;neighbors _neighbors;}
};2. 解题
2.1 DFS
class Solution {Node* visited[101] {NULL};
public:Node* cloneGraph(Node* node) {if(!node) return NULL;int size node-neighbors.size();Node *root new Node(node-val, vectorNode* {});visited[node-val] root;for (int i 0; i size; i) {if (!visited[node-neighbors[i]-val])root-neighbors.push_back(cloneGraph(node-neighbors[i]));elseroot-neighbors.push_back(visited[node-neighbors[i]-val]);}return root;}
};2.2 BFS
class Solution {bool visited[101] {0};
public:Node* cloneGraph(Node* node) {if(!node) return NULL;unordered_mapint, Node* m;//新节点值和它自己的指针unordered_mapNode*, vectorint nhb;//一个节点对应的邻居的节点值queueNode* q;q.push(node);Node *root, *ans;visited[node-val] 1;int i -1, n;while(!q.empty()){n q.front()-neighbors.size();root new Node(q.front()-val, vectorNode* {});if(i -1)ans root;m[q.front()-val] root;for(i 0; i n; i){nhb[root].push_back(q.front()-neighbors[i]-val);if(!visited[q.front()-neighbors[i]-val]){q.push(q.front()-neighbors[i]);visited[q.front()-neighbors[i]-val] 1;}}q.pop();}for(auto it nhb.begin(); it ! nhb.end(); it){n it-second.size();for(i 0; i n; i){it-first-neighbors.push_back(m[it-second[i]]);}}return ans;}
};
