Re: [問題] ancestry problem

[ferng1021 (菘~~~)]

我有一個想法耶

先對那棵tree做一次DFS

並紀錄每一點的進入和離開時間

進入時間指的是從parent走到它的時間

離開時間指的是從它走回parent的時間

以右圖為例                                     Ａ
                                              ／＼
DFS順序： ABDBEBACA                          Ｂ　Ｃ
                                            ／＼
時間    A     B     C     D     E       　 Ｄ　Ｅ

進(t1)  1     2     8     3     5

出(t2)  9     6     8     3     5

如果 X 是 Y 的祖先

則 X.t1 < Y.t1 && X.t2 > Y.t2

DFS : O(n)

兩次整數比大小 : O(1)   （如果這也要說成是log n 那我也沒辦法Orz）

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.229.110.38
推 march20:這是對的, 我們之前提的都是在找 common ancestor
推 march20:看來是 over-killing 了 XD
推 march20:O(n) 的問題應該是不用考慮, 因為counter 最多跳到 n
推 march20:一個樹的 node 數 (也就是 n ) 應該是可以放得下沒問題
推 march20:做 comparison 確實也只要 O(1)
推 Astar:偷推強者
推 seanwu:推大強者
推 LinkCar:強大！
推 a127a127:推強者                                      id斜堆= =
推 jeunder:解得真漂亮! 佩服... Orz