Re: 痛经帖 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

Re: 痛经帖 (转载)

Re: 痛经帖 (转载)# Joke - 肚皮舞运动

a*a2011-12-13 08:12

1 楼

write a function to copy a DAG.
class Node {
int value;
vector neighbors;
};
Node *copyGraph(Node *root) {
// add code here
}

t*y2011-12-13 08:12

2 楼

【以下文字转载自 NewYork 讨论区】
发信人: lulushz (lulushz), 信区: NewYork
标题: Re: 痛经帖
发信站: BBS 未名空间站 (Mon Dec 12 20:39:12 2011, 美东)
你这小姑娘，哎呀，不是打篮球这种运动啦，是指那个那个二人运动啦！
你没听老人常说痛经呀，结婚以后就好了；不然就说生完孩子就好了。。。

p*22011-12-13 08:12

3 楼

DFS就可以了吧？

i*a2011-12-13 08:12

4 楼

哦, 是乒乓球

【在 t*******y 的大作中提到】

: 【以下文字转载自 NewYork 讨论区】
: 发信人: lulushz (lulushz), 信区: NewYork
: 标题: Re: 痛经帖
: 发信站: BBS 未名空间站 (Mon Dec 12 20:39:12 2011, 美东)
: 你这小姑娘，哎呀，不是打篮球这种运动啦，是指那个那个二人运动啦！
: 你没听老人常说痛经呀，结婚以后就好了；不然就说生完孩子就好了。。。

a*a2011-12-13 08:12

5 楼

http://en.wikipedia.org/wiki/Directed_acyclic_graph
就拿这个graph为例，能具体说说怎么用DFS吗？

【在 p*****2 的大作中提到】

: DFS就可以了吧？

l*z2011-12-13 08:12

6 楼

pia~~~~~
TD哥，未经本人同意私自转载，你得赔我个包子！！
人家说的实话嘛，你男的，老太太们才不给你传授这些呢！切！！

【在 t*******y 的大作中提到】

q*c2011-12-13 08:12

7 楼

BFS, DFS 都可以，这题关键是考怎么copy links.

s*a2011-12-13 08:12

8 楼

哦，原来如此

p*22011-12-13 08:12

9 楼

这个图只给一个节点不行吧？根本连不全。

【在 a****a 的大作中提到】

: http://en.wikipedia.org/wiki/Directed_acyclic_graph
: 就拿这个graph为例，能具体说说怎么用DFS吗？

d*u2011-12-13 08:12

10 楼

同意，如果有个节点只有out edge没有in edge，那这个节点拷贝不到。。。

【在 p*****2 的大作中提到】

:
: 这个图只给一个节点不行吧？根本连不全。

a*a2011-12-13 08:12

11 楼

随便画了个简单的DAG，如下图，
如果用DFS的话，假如我用一个queue,
enqueue root, 然check队列是否为空，不为空就enqueue children(neighbors),
在dequeue node 2的时候，enqueue node 4&5,
在dequeue node 3的时候，不应该enqueue node 5，对吧？因为5已经被访问了，如何
记录这个Node是不是已经被访问过呢（不改动原本的DS）。
想到一个方法是可以用一个数组保存所有被访问过的Node地址，每次进队看是不是在这
个数组里。
如果用递归来做应该也是可行的吧。
class Node{
public:
int value;
vector neighbors;
};
vector visited;
bool isNodeVisited(Node *n)
{
vector::iterator it;
it = find(visited.begin(), visited.end(), n);
return it != visited.end();
}
Node *copyGraph(Node* root) {
if (root) return NULL;
Node* newR = new Node;
newR->value = root->value;
vector& nei = root.neighbors;
vector newNei;
for (int i=0; i{
if (!isNodeVisited(nei[i])){
newNei.push_back(copyGraph(nei[i]));
}
}
newR->neighbors = newNei;
return newR;
}
求前辈们指教！

c*p2011-12-13 08:12

12 楼

建个子类？

【在 a****a 的大作中提到】

: 随便画了个简单的DAG，如下图，
: 如果用DFS的话，假如我用一个queue,
: enqueue root, 然check队列是否为空，不为空就enqueue children(neighbors),
: 在dequeue node 2的时候，enqueue node 4&5,
: 在dequeue node 3的时候，不应该enqueue node 5，对吧？因为5已经被访问了，如何
: 记录这个Node是不是已经被访问过呢（不改动原本的DS）。
: 想到一个方法是可以用一个数组保存所有被访问过的Node地址，每次进队看是不是在这
: 个数组里。
: 如果用递归来做应该也是可行的吧。
: class Node{

r*b2011-12-13 08:12

13 楼

We can first numbering the nodes of the DAG, and then create a list of new
nodes and re-construct the links:
Here is an implementation for DAG clone:
http://basicalgos.blogspot.com/2012/03/27-clone-directed-acycli

【在 a****a 的大作中提到】

: write a function to copy a DAG.
: class Node {
: int value;
: vector neighbors;
: };
: Node *copyGraph(Node *root) {
: // add code here
: }

p*22011-12-13 08:12

14 楼

DFS应该不需要Queue吧？递归就行了吧？

【在 a****a 的大作中提到】

g*y2011-12-13 08:12

15 楼

用queue不就是bfs了吗

【在 p*****2 的大作中提到】

:
: DFS应该不需要Queue吧？递归就行了吧？

p*22011-12-13 08:12

16 楼

是呀。

【在 g***y 的大作中提到】

: 用queue不就是bfs了吗

s*n2011-12-13 08:12

17 楼

queue + hashTable 也就是bfs了, 还有其他trick吗？

a*a2011-12-13 08:12

18 楼

你那counter没变啊，ms需要改一下

【在 r*****b 的大作中提到】

: We can first numbering the nodes of the DAG, and then create a list of new
: nodes and re-construct the links:
: Here is an implementation for DAG clone:
: http://basicalgos.blogspot.com/2012/03/27-clone-directed-acycli

g*e2011-12-13 08:12

19 楼

只要按照topological order来traverse一遍就行了吧
先复制root
从root开始，查看neighbour中刨去跟root相连的edge外只有输出的node,复制该node。
然后重复寻找这样的Node,一直到完成。
当然，Input root可能有好几个。

D*g2011-12-13 08:12

20 楼

可以maintain一个从原图node到copy node的map，大概是这样:
public static class Node {
public int data;
public List next;
}
static Node copyNode(final Node n) {
if (n == null) return null;
return copyNode(n, new HashMap());
}
static Node copyNode(final Node n, final Map m) {
if (n == null) return null;
if (m.containsKey(n)) return m.get(n);
Node newNode = new Node();
m.put(n, newNode);
newNode.data = n.data;
newNode.next = new ArrayList();
for (int i = 0; i < n.next.size(); ++i) {
newNode.add(copyNode(n.next.get(i), m));
}
}

【在 a****a 的大作中提到】

: write a function to copy a DAG.
: class Node {
: int value;
: vector neighbors;
: };
: Node *copyGraph(Node *root) {
: // add code here
: }