注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

离线tarjan算法(LCA)  

2014-03-31 21:37:34|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
对于LCA(最近公共最先的问题),有两种较快解法,一种是log(N)的倍增,一种就是tarjan。O(N+K)k是询问次数。
倍增以后再讲,先谈谈tarjan吧:

离线算法 Tarjan

利用并查集优越的时空复杂度,我们可以实现LCA问题的O(n+Q)算法,这里Q表示询问的次数。Tarjan算法基于深度优先搜索的框架,对于新搜索到 的一个结点,首先创建由这个结点构成的集合,再对当前结点的每一个子树进行搜索,每搜索完一棵子树,则可确定子树内的LCA询问都已解决。其他的LCA询 问的结果必然在这个子树之外,这时把子树所形成的集合与当前结点的集合合并,并将当前结点设为这个集合的祖先。之后继续搜索下一棵子树,直到当前结点的所 有子树搜索完。这时把当前结点也设为已被检查过的,同时可以处理有关当前结点的LCA询问,如果有一个从当前结点到结点v的询问,且v已被检查过,则由于 进行的是深度优先搜索,当前结点与v的最近公共祖先一定还没有被检查,而这个最近公共祖先的包涵v的子树一定已经搜索过了,那么这个最近公共祖先一定是v 所在集合的祖先。
----------------以上摘自百度百科。
为什么称它是离线算法呢,因为他需要将每两个点的询问事先存储起来,类似于边表的存。tarjan是用DFS+并查集的,首先对于某个点,我们是先做它和儿子的关系再和它的爸爸合并集合的,否则它儿子的一些LCA询问会指向它的爸爸,导致错误。其次做完这些我们需要做与这个节点相关的询问,而另一个点询问的点必须是已经搜到过的,这样才会有父亲值,如当前T节点儿子K,与之相关的询问K,L,L不是T节点的儿子,那么无论是T祖先还是没搜到的都能出正解了。当前T和L的最近公共祖先一定是FA[L];dis记录到根节点的距离,那么这组答案就是dis[T]+dis[L]-2*dis[FA[L]];
大概的框架:
LCA(W)
vist[w]=true;fa[w]=w;
for 所有与w相连的结点c   if  (!vist[c]){
                                                      dis[c]=dis[w]+这条边的距离。
                                                     LCA(c);
                                                     fa[c]=w;
                                                     一定要做完c以后再合并;
                                                              }
for 所有与w相关联的结点c  if  (vist[c])
                                {
                               int u=get(c);
                               记录答案ans=dis[w]+dis[c]-2*dis[u];
                               }
  评论这张
 
阅读(40)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018