作者ferng1021 (菘~~~)
站內Prob_Solve
標題Re: [問題] ancestry problem
時間Sun Jun 24 01:28:44 2007
我有一個想法耶
先對那棵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
1F：推 march20:這是對的, 我們之前提的都是在找 common ancestor 06/24 02:14
2F：推 march20:看來是 over-killing 了 XD 06/24 02:14
3F：推 march20:O(n) 的問題應該是不用考慮, 因為counter 最多跳到 n 06/24 02:15
4F：推 march20:一個樹的 node 數 (也就是 n ) 應該是可以放得下沒問題 06/24 02:16
5F：推 march20:做 comparison 確實也只要 O(1) 06/24 02:16
6F：推 Astar:偷推強者 06/24 09:12
7F：推 seanwu:推大強者 06/24 12:29
8F：推 LinkCar:強大！ 06/24 23:39
9F：推 a127a127:推強者 id斜堆= = 06/25 05:50
10F：推 jeunder:解得真漂亮! 佩服... Orz 06/25 13:40
11F：推 netsphere:簡單明瞭....強者... 08/06 19:34
12F：推 yqln95:強者，還利用到post-DFS的特性來解掉這個問題! 08/15 17:50