Re: [問題] ancestry problem

看板Prob_Solve作者 (菘~~~)時間17年前 (2007/06/24 01:28), 編輯推噓12(12推 0噓 0→)
留言12則, 8人參與, 最新討論串14/15 (看更多)
我有一個想法耶 先對那棵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
推
06/24 02:14, , 1F
這是對的, 我們之前提的都是在找 common ancestor
06/24 02:14, 1F
推
06/24 02:14, , 2F
看來是 over-killing 了 XD
06/24 02:14, 2F
推
06/24 02:15, , 3F
O(n) 的問題應該是不用考慮, 因為counter 最多跳到 n
06/24 02:15, 3F
推
06/24 02:16, , 4F
一個樹的 node 數 (也就是 n ) 應該是可以放得下沒問題
06/24 02:16, 4F
推
06/24 02:16, , 5F
做 comparison 確實也只要 O(1)
06/24 02:16, 5F
推
06/24 09:12, , 6F
偷推強者
06/24 09:12, 6F
推
06/24 12:29, , 7F
推大強者
06/24 12:29, 7F
推
06/24 23:39, , 8F
強大！
06/24 23:39, 8F
推
06/25 05:50, , 9F
推強者 id斜堆= =
06/25 05:50, 9F
推
06/25 13:40, , 10F
解得真漂亮! 佩服... Orz
06/25 13:40, 10F
推
08/06 19:34, , 11F
簡單明瞭....強者...
08/06 19:34, 11F
推
08/15 17:50, , 12F
強者，還利用到post-DFS的特性來解掉這個問題!
08/15 17:50, 12F
‣ 更多 ferng1021 的文章
文章代碼(AID): #16VLXEO8 (Prob_Solve)
討論串 (同標題文章)
完整討論串 (本文為第 14 之 15 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共15篇)
‣ 更多 ferng1021 的文章
文章代碼(AID): #16VLXEO8 (Prob_Solve)