LCA最近公共祖先(tarjan离线)
求最近公共祖先的方法有三个:tarjan离线,倍增在线,RMQ。tarjan离线的方法理解起来较为简单。
- 先选择一个节点u为根节点,从根节点开始搜索。(标记u已访问过)
- 遍历该点u的所有儿子节点v,并标记v已访问过。
- 若v还有儿子节点,对v重复ii操作,否则进入下一操作。
- 把v合并到u上(并查集)。
- 把当前的点设为u,遍历与u有询问关系的节点v。
- 如果v在之前已经被访问过,那么u和v的最近公共祖先就是v通过并查集合并后的父亲节点(注意是合并后),即当前的find(v)
二.tarjan算法的伪代码:
Tarjan(u) //根节点u
{
for each(u,v)
{
Tarjan(v); //v还有儿子节点
join(u,v); //把v合并到u上
vis[v]=1; //访问标记
}
for each(u,v) //遍历与u有询问关系的节点v
{
if(vis[v])
{
ans=find(v);
}
}
}
三. Tarjan算法模拟
1.先取1为根节点, 发现其有两个子节点2和3,先搜索2,又发现2有两个子节点4和5,先搜索4,4也有两个子节点6和7,先搜索6,这时发现6没有子节点了,然后寻找与其有询问关系的节点,发现5和7均与6有询问关系,但都没被访问过。所以返回并标记vis[6]=1,pre[6]=4;
2.接着搜索7,发现7没有子节点,然后寻找与其有询问关系的节点,发现6与其有询问关系,且vis[6]=1,所以LCA(6,7)=find(6)=4。结束并标记vis[7]=1,pre[7]=4;
3.现在节点4已经搜完,且没有与其有询问关系的节点,vis[4]=1,pre[4]=2;
4.搜索5,发现其有子节点8,搜索8,发现8没有子节点,然后寻找与其有询问关系的节点,也没有,于是返回,且vis[5]=1,pre[8]=5;
5.节点5已经搜完,发现有两个与其有询问关系的节点6和7,且vis[6]=1,所以LCA(5,6)=find(6)=2;因为vis[7]=1,所以LCA(5,7)=find(7)=2;遍历完毕返回,标记vis[5]=1,pre[5]=2;
(find过程:pre[7]=4,pre[4]=2 ==》2 )
6.节点2已经搜完,发现有一个与其有询问关系的节点7,且vis[7]=1,故LCA(2,7)=find(7)=2。遍历完毕,标记vis[2]=1,pre[2]=1;
7.接着搜索3,没有子节点,发现有一个与其有询问关系的节点5,因为vis[5]=1,所以LCA(3,5)=find(5)=1;遍历结束,标记vis[3]=1,pre[3]=1;
(find过程:pre[5]=2,pre[2]=1 ==》1 )
8.这时返回到了节点1,它没有与之有询问关系的点了,且其pre[1]=1,搜索结束。
完成求最小公共祖先的操作。
四.Tarjan算法的代码由于LCA的题目千变万化,下面给出最基础的模板(给出一系列边用邻接表保存,把询问也用邻接表保存,只求LCA,不维护其他值)
void Tarjan(int now)
{
vis[now]=1;
for(int i=head1[now];i!=-1;i=e1[i].next)
{
int t=e1[i].t;
if(vis[t]==0)
{
Tarjan(t);
join(now,t);
}
}
for(int i=head2[now];i!=-1;i=e2[i].next)
{
int t=e2[i].t;
if(vis[t]==1)
{
e2[i].lca=find(t);
e2[i^1].lca=e2[i].lca;
}
}
}
五.例题:http://poj.org/problem?id=1330
就是 输入cas 后 有cas组数据 输入 n 再输入n-1 条边 之后输入x y 问x y的最近公共祖先是什么
裸的LCA:
代码:
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
#define Size 11111 //节点个数
vector<int> node[Size],que[Size];
int n,pare[Size],anse[Size],in[Size],rank[Size];
int vis[Size];
void init()
{
int i;
for(i=1;i<=n;i++)
{
node[i].clear();
que[i].clear();
rank[i]=1;
pare[i]=i;///
}
memset(vis,0,sizeof(vis));
memset(in,0,sizeof(in));
memset(anse,0,sizeof(anse));
}
int find(int nd)//并查集操作 不解释
{
return pare[nd]==nd?nd:pare[nd]=find(pare[nd]);
}
int Union(int nd1,int nd2)//并查集操作 不解释
{
int a=find(nd1);
int b=find(nd2);
if(a==b) return 0;
else if(rank[a]<=rank[b])
{
pare[a]=b;
rank[b]+=rank[a];
}
else
{
pare[b]=a;
rank[a]+=rank[b];
}
return 1;
}
void LCA(int root)
{
int i,sz;
anse[root]=root;//首先自成一个集合
sz=node[root].size();
for(i=0;i<sz;i++)
{
LCA(node[root][i]);//递归子树
Union(root,node[root][i]);//将子树和root并到一块
anse[find(node[root][i])]=root;//修改子树的祖先也指向root
}
vis[root]=1;
sz=que[root].size();
for(i=0;i<sz;i++)
{
if(vis[que[root][i]])
{
printf("%d\n",anse[find(que[root][i])]);///root和que[root][i]所表示的值的最近公共祖先
return ;
}
}
return ;
}
int main()
{
int cas,i;
scanf("%d",&cas);
while(cas--)
{
int s,e;
scanf("%d",&n);
init();
for(i=0;i<n-1;i++)
{
scanf("%d %d",&s,&e);
if(s!=e)
{
node[s].push_back(e);
// node[e].push_back(s);
in[e]++;
}
}
scanf("%d %d",&s,&e);
que[s].push_back(e);
que[e].push_back(s);
for(i=1;i<=n;i++) if(in[i]==0) break;//寻找根节点
// printf("root=%d\n",i);
LCA(i);
}
return 0;
}
参考:http://blog.csdn.net/hnust_xiehonghao/article/details/9109295
http://blog.csdn.net/lw277232240/article/details/77017517
http://blog.csdn.net/my_sunshine26/article/details/72717112
上一篇: (算法练习)——散列
下一篇: 【JMicro】1. JMicro简介