d********w
发帖数: 363 | 1 大家看我这样写对么，dfs来做，map来保存是否之前遇过。
1 struct Node {
2 int val;
3 vector neighbors;
4 }
5
6 Node* clone(Node *root, HashMap& map) {
7 if (root == NULL) {
8 return NULL;
9 }
10 if (map.find(root) != map::end()) {
11 return map[root];
12 }
13
14 Node* p = new Node();
15 p->val = root->val;
16 p->neighbors = new vector();
17 vector& v = p->neighbors;
18 for (int i=0; ineighbors.size(); i++) {
19 Node* orig = root->neighbors[i];
20 v.add(clone(orig, map));
21 }
22 map[root] = p;
23 return p;
24 } |
p*****2
发帖数: 21240 | 2
打牛再面F呀？
【在 d********w 的大作中提到】
: 大家看我这样写对么，dfs来做，map来保存是否之前遇过。
: 1 struct Node {
: 2 int val;
: 3 vector neighbors;
: 4 }
: 5
: 6 Node* clone(Node *root, HashMap& map) {
: 7 if (root == NULL) {
: 8 return NULL;
: 9 }
|
t******e
发帖数: 98 | 3 lz算法没问题。我的程序如下请指教：
// copy graph
struct node
{
int id;
vector adj;
node(int id) : id(id){}
};
map hash;
node* copy(node* x)
{
if(!x) return 0;
if(hash.count(x) != 0) return hash[x];
hash[x] = new node(x->id);
node* y = hash[x];
for(int i = 0; i < x->adj.size(); ++i){
y->adj.push_back(copy(x->adj[i]));
}
return y;
} |
r*****b
发帖数: 310 | 4 A few questions here:
1. Do we need line 16
2. Shall we move line 22 before the loop that starts from line 18?
Here is my implementation:
http://basicalgos.blogspot.com
【在 d********w 的大作中提到】
: 大家看我这样写对么，dfs来做，map来保存是否之前遇过。
: 1 struct Node {
: 2 int val;
: 3 vector neighbors;
: 4 }
: 5
: 6 Node* clone(Node *root, HashMap& map) {
: 7 if (root == NULL) {
: 8 return NULL;
: 9 }
|
s******n
发帖数: 3946 | |
z*****n
发帖数: 447 | 6 算法应该没错，语法好像有2个小问题
1） HashMap 第二个参数Node *其实没有用上，用C++的话，可以改
成
unordered_set
2） Line 17， & 应该是 *
【在 d********w 的大作中提到】
: 大家看我这样写对么，dfs来做，map来保存是否之前遇过。
: 1 struct Node {
: 2 int val;
: 3 vector neighbors;
: 4 }
: 5
: 6 Node* clone(Node *root, HashMap& map) {
: 7 if (root == NULL) {
: 8 return NULL;
: 9 }
|
x****g
发帖数: 325 | 7 line 22 should be moved before the loop.
【在 d********w 的大作中提到】
: 大家看我这样写对么，dfs来做，map来保存是否之前遇过。
: 1 struct Node {
: 2 int val;
: 3 vector neighbors;
: 4 }
: 5
: 6 Node* clone(Node *root, HashMap& map) {
: 7 if (root == NULL) {
: 8 return NULL;
: 9 }
|
