poj 2104 2761 树状数据结构
poj 2117 求割点的tarjan算法

LCA的tarjan算法的理解

scturtle posted @ 2011年10月08日 11:08 in algorithm , 19714 阅读

tarjan算法的步骤是(当dfs到节点u时):
1 在并查集中建立仅有u的集合,设置该集合的祖先为u
1 对u的每个孩子v:
   1.1 tarjan之
   1.2 合并v到父节点u的集合,确保集合的祖先是u
2 设置u为已遍历
3 处理关于u的查询,若查询(u,v)中的v已遍历过,则LCA(u,v)=v所在的集合的祖先
 
举例说明(非证明):


假设遍历完10的孩子,要处理关于10的请求了
取根节点到当前正在遍历的节点的路径为关键路径,即1-3-8-10
集合的祖先便是关键路径上距离集合最近的点
比如此时:
    1,2,5,6为一个集合,祖先为1,集合中点和10的LCA为1
    3,7为一个集合,祖先为3,集合中点和10的LCA为3
    8,9,11为一个集合,祖先为8,集合中点和10的LCA为8
    10,12为一个集合,祖先为10,集合中点和10的LCA为10
你看,集合的祖先便是LCA吧,所以第3步是正确的
道理很简单,LCA(u,v)便是根至u的路径上到节点v最近的点

为什么要用祖先而且每次合并集合后都要确保集合的祖先正确呢?
因为集合是用并查集实现的,为了提高速度,当然要平衡加路径压缩了,所以合并后谁是根就不确定了,所以要始终保持集合的根的祖先是正确的
关于查询和遍历孩子的顺序:
wikipedia上就是上文中的顺序,很多人的代码也是这个顺序
但是网上的很多讲解却是查询在前,遍历孩子在后,对比上文,会不会漏掉u和u的子孙之间的查询呢?
不会的
如果在刚dfs到u的时候就设置u为visited的话,本该回溯到u时解决的那些查询,在遍历孩子时就会解决掉了
这个顺序问题就是导致我头大看了很久这个算法的原因,也是絮絮叨叨写了本文的原因,希望没有理解错= =

最后,为了符合本blog风格,还是贴代码吧:

int f[maxn],fs[maxn];//并查集父节点 父节点个数
bool vit[maxn];
int anc[maxn];//祖先
vector<int> son[maxn];//保存树
vector<int> qes[maxn];//保存查询
typedef vector<int>::iterator IT;

int Find(int x)
{
    if(f[x]==x) return x;
    else return f[x]=Find(f[x]);
}
void Union(int x,int y)
{
    x=Find(x);y=Find(y);
    if(x==y) return;
    if(fs[x]<=fs[y]) f[x]=y,fs[y]+=fs[x];
    else f[y]=x,fs[x]+=fs[y];
}

void lca(int u)
{
    anc[u]=u;
    for(IT v=son[u].begin();v!=son[u].end();++v)
    {
        lca(*v);
        Union(u,*v);
        anc[Find(u)]=u;
    }
    vit[u]=true;
    for(IT v=qes[u].begin();v!=qes[u].end();++v)
    {
        if(vit[*v])
            printf("LCA(%d,%d):%d\n",u,*v,anc[Find(*v)]);
    }
}

ref:
http://purety.jp/akisame/oi/TJU/
http://en.wikipedia.org/wiki/Tarjan%27s_off-line_least_common_ancestors_algorithm
http://techfield.us/blog/2008/11/lowest_common_ancester_tarjan_alogrithm/

fly2best 说:
2012年7月28日 22:35

好文~~
thanks very much~
那个图非常能说明问题~
一下子就看懂了。

指出一个小小的疏漏
lca
应该加一句 f[u] = u; //初始化集合

muye5 说:
2013年3月14日 16:14

冒昧问一句:这里的Union(u,*v);有什么用,还是说在别的情况下有用?不能直接把这两句:
Union(u,*v);
anc[Find(u)]=u;
变成
anc[Find(v)]=u;么?不是很理解这里

Avatar_small
scturtle 说:
2013年3月14日 20:30

唔,可以,感觉先 union 的话树可能会更平衡一些

害羞 说:
2014年5月15日 11:32

我想问下 怎么样保证祖先是最近祖先呢 那条关键路径怎么形成 = =

Avatar_small
scturtle 说:
2014年5月16日 08:15

Union(u,*v); anc[Find(u)]=u 这里,关键路径就是 DFS 时递归栈里节点

害羞 说:
2014年5月17日 17:07

想了很久 今天想明白了 新手 谢谢楼主~

ddd 说:
2015年9月12日 13:13

dddddddddddddddddddddddddddddddddd

there is a dream 说:
2015年9月12日 13:14

扯毛啊


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter