l*****z
发帖数: 3022 | 1 有N个人，编号从0到N-1。给一个数组，a[N][2] ，数组的值在 -1 到 N-1 . a[i][0]
， a[i][1] 分别为i 的父母的编号。 如果父或母不在 0到N-1，则值为 -1。
问给2个人，i, j 问他们有没有血缘关系。
完全没头绪啊！ |
p*****2
发帖数: 21240 | |
b*****n
发帖数: 618 | |
p*****2
发帖数: 21240 | 4
不需要hashmap，一个boolean array就可以了。
【在 b*****n 的大作中提到】
: HashMap + DFS ?
|
l*****z
发帖数: 3022 | 5 分别对i 和j做DFS, boolean array有一个match就行了。 这个方法不错。 |
b*****n
发帖数: 618 | 6 o...了解了，需要两个boolean array吗？像兄弟姐妹这种关系怎么处理比较好？
【在 p*****2 的大作中提到】
:
: 不需要hashmap，一个boolean array就可以了。
|
b*****n
发帖数: 618 | 7 明白了。。。这个好
【在 l*****z 的大作中提到】
: 分别对i 和j做DFS, boolean array有一个match就行了。 这个方法不错。
|
g*******s
发帖数: 2963 | 8 我觉得用一个长度N的array的boolean 就可以了把？
任意一边dps遍历到一个，flip那个bit。
如果当前被flip的是i或j，这样i和j是直系祖孙关系
令一种是当前要flip的已经被flip过了，这说明i和j是远房亲戚，类似与找lowest
common parant问题 |
