hihoCoder 最近公共祖先2 之 DFS + 并查集 法

October 18, 2014 | 09:49

第一次玩 hihoCoder, 题目就是一个裸的 LCA  问题, 只不过结点的名字不是数字而是字符串, 用两个 map 映射一下就可以转化为数字来处理.

以前做 LCA 都是用的 Tarjan 离线算法, 这次 hihoCoder 给出一种 dfs + 并查集大法, 我颇为好奇. 然后 AC 了之后 Google 了一下 Tarjan 离线算法(太久没做 LCA的题目忘了 Tarjan 长啥样了), 发现其实 hohoCoder 只是没提到 Tarjan 这个名词, 本质都是一样的算法呐!

在这道题中, 离线算法的好处体现在:

  • 如果用传统在线算法, 对于询问 (u, v) 需要找到 u-->root 的路径和 v-->root 的路径, 然后就能找到 answer. 但是这个回溯的过程是 O(N), 如果有 M 个询问, 整个复杂度就是 O(NM). 离线算法解决了这个问题, 在 dfs 的过程中, 碰到和谁相关的询问就立马给他一个回答, 理论复杂度是 O(N).

但是由于我没想好如何快速找到和当前 dfs 到的结点 u 相关的询问, 我第一次枚举了每一个询问来查找, 最后就超时了. 然后我给那些询问建立了一个 map<int, vector<int> >, 这样能优化不少, 最后 AC, 但是不知道有没有更快的方法, 因为这样的速度虽然接近 O(N), 但是还是达不到.

代码如下:

 

 

( 转载请注明: Jecvay Notes )

说几句