作者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