a********r
发帖数: 218 | 1 Input
parent 15, children 1 2
parent 1, no children
parent 2, no children
parent 9, children 4
parent 10, children 15 9
parent 4, no children
要找出最后的root, 这个例子的答案是10 | d*******n
发帖数: 43 | 2 Union Find?
【在 a********r 的大作中提到】
: Input
: parent 15, children 1 2
: parent 1, no children
: parent 2, no children
: parent 9, children 4
: parent 10, children 15 9
: parent 4, no children
: 要找出最后的root, 这个例子的答案是10
| k****r
发帖数: 421 | | a********r
发帖数: 218 | 4 根据Input 可以得到下面的tree (每个父母不一定只有两个儿子， 跟像trie)
10
/
15 9
/
1 2 4
所以答案是10
【在 k****r 的大作中提到】
: 哎，俺最怕这类题。。。
| l******n
发帖数: 9344 | 5 随便找一个node,然后一直找parent,就是标准的find function
input写成parent数组
parent = [15:[1,2],1:[],2,[],....]
def find(x):
if parent[x]:
x = parent[x][0]
return(x)
【在 a********r 的大作中提到】
: Input
: parent 15, children 1 2
: parent 1, no children
: parent 2, no children
: parent 9, children 4
: parent 10, children 15 9
: parent 4, no children
: 要找出最后的root, 这个例子的答案是10
| g*****a
发帖数: 319 | 6 Topological sort也可以找到
【在 l******n 的大作中提到】
: 随便找一个node,然后一直找parent,就是标准的find function
: input写成parent数组
: parent = [15:[1,2],1:[],2,[],....]
: def find(x):
: if parent[x]:
: x = parent[x][0]
: return(x)
| g**v
发帖数: 19 | 7 还需要sort吗？这个题感觉条件不全啊 会不会有几个root？indeg是0的是不是就是
root？
: Topological sort也可以找到
【在 g*****a 的大作中提到】
: Topological sort也可以找到
| G****A
发帖数: 4160 | 8 longtian 说的方法肯定可以
但最简单的应该是线性扫一遍，ingress degree为零的点就是root | l******n
发帖数: 9344 | 9 扫一遍是O(n),找parent是O(h)，h是tree的高度
【在 G****A 的大作中提到】
: longtian 说的方法肯定可以
: 但最简单的应该是线性扫一遍，ingress degree为零的点就是root
| a********r
发帖数: 218 | 10 如果没找到共同的root, 就返回nullptr
【在 g**v 的大作中提到】
: 还需要sort吗？这个题感觉条件不全啊 会不会有几个root？indeg是0的是不是就是
: root？
:
:
: Topological sort也可以找到
:
| a********r
发帖数: 218 | 11 如果没找到共同的root, 就返回nullptr
【在 g**v 的大作中提到】
: 还需要sort吗？这个题感觉条件不全啊 会不会有几个root？indeg是0的是不是就是
: root？
:
:
: Topological sort也可以找到
:
|
|
