i***h
发帖数: 12655 | |
N********n
发帖数: 8363 | 2 What's the node structure? Is it allowed to mark if a node is visited?
【在 i***h 的大作中提到】
: 不得改动原图
: 有比两次深度遍历更好的办法么?
|
i***h
发帖数: 12655 | 3 struct Node {
int data;
Node * children;
}
写一个函数
Node* copyGraph(Node* g);
不能动原图g的东西，你说的mark 大概是不行的，我是自己存个记录．
【在 N********n 的大作中提到】
: What's the node structure? Is it allowed to mark if a node is visited?
|
s*****d
发帖数: 43 | 4 extra data structure allowed?
Is graph cycle-free or not? |
N********n
发帖数: 8363 | 5
What's the input? Is it actually a single-linked list that might have
a circle or a graph. If it's a graph, then I need to know the data
structure of the input.
【在 i***h 的大作中提到】
: struct Node {
: int data;
: Node * children;
: }
: 写一个函数
: Node* copyGraph(Node* g);
: 不能动原图g的东西，你说的mark 大概是不行的，我是自己存个记录．
|
i***h
发帖数: 12655 | 6 Node* copyGraph(Node* g);
输入就是原图起点啊，保证是连通图，每个节点可以有任意多个向外链接
可能有循环链接
【在 N********n 的大作中提到】
: What's the node structure? Is it allowed to mark if a node is visited?
|
N********n
发帖数: 8363 | 7
"每个节点可以有任意多个向外链接"
How is that possible with a node definition like below? There is
only one children pointer out.
struct Node {
int data;
Node * children;
}
【在 i***h 的大作中提到】
: Node* copyGraph(Node* g);
: 输入就是原图起点啊，保证是连通图，每个节点可以有任意多个向外链接
: 可能有循环链接
|
i***h
发帖数: 12655 | 8 不好意思，错大发了
那个children是一个链表，但每个节点要另外定义：
struct Child {
Node *n;
Child *next;
}
【在 i***h 的大作中提到】
: Node* copyGraph(Node* g);
: 输入就是原图起点啊，保证是连通图，每个节点可以有任意多个向外链接
: 可能有循环链接
|
