Open
Description
这个题目做的很晕,可能状态不好
思路:
考虑bfs,队列中为要拷贝的Node,遍历其邻居,如果邻居已经被访问,其地址已经被存到map中,加入其拷贝地址即可,如果不在map中,则生产一个地址加入map,同时需要注意的是每次加入队列中的都是未被访问的
dfs也是一样的原理,未访问过的就在map生成一个地址,并且进行递归
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
unordered_map<Node*, Node*> m;
unordered_set<Node*> f;
Node* cloneGraph(Node* node) {
if(node == nullptr) return nullptr;
queue<Node*> q;
Node* a, *h;
a = new Node();
a->val = node->val;
m[node] = a;
q.push(node);
while(!q.empty()){
int n = q.size();
for(int i = 0; i < n; i++){
auto t = q.front();
q.pop();
auto c = m[t];
for(int j = 0; j < t->neighbors.size(); j++){
if(m.count(t->neighbors[j]) == 0){
auto x = new Node();
x->val = t->neighbors[j]->val;
m[t->neighbors[j]] = x;
q.push(t->neighbors[j]);
}
c->neighbors.push_back(m[t->neighbors[j]]);
}
}
}
return m[node];
}
};
dfs
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
unordered_map<Node*, Node*> m;
void dfs(Node* h){
for(int i = 0; i < h->neighbors.size(); i++){
if(m.count(h->neighbors[i]) == 0){
auto x = new Node();
x->val = h->neighbors[i]->val;
m[h->neighbors[i]] = x;
dfs(h->neighbors[i]);
}
m[h]->neighbors.push_back(m[h->neighbors[i]]);
}
}
Node* cloneGraph(Node* node) {
if(node == nullptr) return nullptr;
Node* a;
a = new Node();
a->val = node->val;
m[node] = a;
dfs(node);
return m[node];
}
};