请教一道G家onsite题。。。 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道G家onsite题。。。

请教一道G家onsite题。。。# JobHunting - 待字闺中

d*i2014-06-02 07:06

1 楼

请问下题如何用有向图来实现？谢谢。
题目：
printing a tree structure with giving collection of pairs of child> relation. Need to first find the root, and validate wether the given
relations is a valid tree, and then printing.
问题一：如何判断有valid tree
问题二：如果print?
例:
给一个set，里面是一堆pair，每个pair里是两个string，一个first，一个second。
如果这堆pair能够构成一个树状结构，按照一定的格式打印这棵树
first-second关系类似paretnt-child关系
eg
set: (a, b) (b, c) (a, d) (d, e) (d, f) (d, g)
树状结构是root = a, root.left = b, root.right = d blah blah
打印结果：[space] 就是一个空格. 1point3acres.com/bbs
a
[space]b
[space][space]c
[space]d
[space][space]e
[space][space]f
[space][space]g.1

c*z2014-06-02 07:06

2 楼

detect cycles? BFS?

l*82014-06-02 07:06

3 楼

一，indegree为0的是root
从root开始dfs，检测是否访问一个节点两次，如果是，就有cycle，不是tree。
二，dfs, 传一个参数表示level.

given

【在 d********i 的大作中提到】

: 请问下题如何用有向图来实现？谢谢。
: 题目：
: printing a tree structure with giving collection of pairs of : child> relation. Need to first find the root, and validate wether the given
: relations is a valid tree, and then printing.
: 问题一：如何判断有valid tree
: 问题二：如果print?
: 例:
: 给一个set，里面是一堆pair，每个pair里是两个string，一个first，一个second。
: 如果这堆pair能够构成一个树状结构，按照一定的格式打印这棵树