本文共 4370 字,大约阅读时间需要 14 分钟。
LCA(Least Common Ancestor),顾名思义,是指在一棵树中,距离两个点最近的两者的公共节点。也就是说,在两个点通往根的道路上,肯定会有公共的节点,我们就是要求找到公共的节点中深度尽量深的点。还可以表示成另一种说法,就是如果把树看成是一个图,这找到这两个点中的最短距离。Tarjan作为离线off-line算法,在程序开始前,需要将所有等待询问的节点对提前存储(非常重要,也是为什么称之为“离线”的原因),然后程序从树根开始执行LCA()。
如图:
下面我将详细解释LCA一般用法:
(1)建立树的表示
程序设计中,用vector<int> node[n]来保存树的结构
- for(i=0;i<n-1;i++)
- {
- scanf("%d %d",&s,&e); /*s,e分别为树上的节点*/
- if(s!=e)
- {
- node[s].push_back(e);
- in[e]++; /*in[n] 节点的入度,目的是找根节点*/
- }
上图执行完这段程序后,结果如图所示:{注:节点的编号和数组下标一一对应}
红色的数字是node[s].size不为0的大小.(整棵树的表示有了哦),是计算出来的哈,写上去是为了便于大家理解。
(2)保存查询,用vector<int> que[n]来保存所要的查询对。
- querynum=某个数;
- while(querynum!=0)
- {
- scanf("%d %d",&s,&e);
- que[s].push_back(e);
- que[e].push_back(s);
- querynum--;
- }
如:分别输入(1,2),(2,4),(2,3),(2,7),(7,8),(5,6)等等等等,也就是你可以输入任意一对树上的节点,你需要查询它们的最近公共祖先。
执行后,que如图下图所示:
注意:红色的数字是为了便于大家理解,计算出来的que[n].size。大家是否注意到图中(1,2),(2,4),(2,3),(2,7),(7,8),(5,6)又分别存成了(2,1),(4,2),(3,2),(7,2),(8,7),(6,5)。这是因为根据LCA离线算法,上面提到的询问(x,y)中,y是已处理过的结点。那么,如果y尚未处理怎么办?所以,只要在查询列表中加入两个询问(x, y)、(y,x),那么就可以保证这两个询问有且仅有一个被处理了(暂时无法处理的那个就pass掉)。
(3)LCA算法
假设为(u,v),u为此时已经搜完的子树的根节点,v的位置就只有两种可能,一种是在u的子树内,另一种就是在其之外。
对于在u的子树内的话,最近公共祖先肯定是可以直接得出为u;
对于在u的子树之外的v,我们已经将v搜过了,且已经知道了v的祖先,那么我们可以根据dfs的思想,v肯定是和u在一颗子树下的,而且这颗子树是使得他们能在一颗子树下面深度最深的。而这个子树的根节点刚好就是v的并查集所保存的祖先。所以对于这种情况的(u,v),它们的最近公共祖先就是v的并查集祖先。关于并查集,。
- int find(int u)
- {
- return pare[u]==u?u:pare[u]=find(pare[u]);
- }
- int Union(int u,int v)
- {
- int a=find(u);
- int b=find(v);
- 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;
-
- }
通过pare[]这个数组,可以找到当前节点的根节点。
最后:
-
- 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(node[root][i],root);
- anse[find(node[root][i])]=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])]);
- return ;
- }
- }
- return ;
- }
根据TarjanLCA的实现算法可以看出,只有当某一棵子树全部遍历处理完成后,才将该子树的根节点标记为已访问(vis[root]=1),假设程序按上面的树形结构进行遍历,首先从节点1开始,然后递归处理根为2的子树,然后递归处理根为5的子树,当子树处理完后,节点5标记为已访问(vis[5]=1),处理和5相关的查询(见程序LCA中的14行,节点2未被访问,跳过),返回,将(5,2)合并,pare[5]=2,。以此类推,当子树2处理完毕后,节点2, 5, 6均已访问;接着要回溯处理3子树,首先被访问的是节点7(因为节点7作为叶子不用深搜,直接处理),接着节点7就会查看所有询问(7, x)的节点对,假如存在(7, 5),因为节点5已经被访问,所以就可以断定(7, 5)的最近公共祖先就是find(5).ancestor,即节点1(因为2子树处理完毕后,子树2和节点1进行了union,find(5)返回了合并后的树的根1,此时树根的ancestor的值就是1)。 建议:大家亲自走一遍程序。
代码:
- #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],querynum;
-
- 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 u)
- {
- return pare[u]==u?u:pare[u]=find(pare[u]);
- }
- int Union(int u,int v)
- {
- int a=find(u);
- int b=find(v);
- 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(node[root][i],root);
- anse[find(node[root][i])]=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])]);
- return ;
- }
- }
- return ;
- }
-
- int main()
- {
- int i;
- scanf("%d",&n,&querynum);
- init();
- for(i=0;i<n-1;i++)
- {
- scanf("%d %d",&s,&e);
- if(s!=e)
- {
- node[s].push_back(e);
- in[e]++;
- }
- }
-
- int find(int u)
- {
- return pare[u]==u?u:pare[u]=find(pare[u]);
- }
- int Union(int u,int v)
- {
- int a=find(u);
- int b=find(v);
- 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;
-
- }
-
- while(querynum!=0)
- {
- scanf("%d %d",&s,&e);
- que[s].push_back(e);
- que[e].push_back(s);
- querynum--;
- }
-
- for(i=1;i<=n;i++) if(in[i]==0) break;
- LCA(i);
- }
- return 0;
- }
- int find(int u)
- {
- return pare[u]==u?u:pare[u]=find(pare[u]);
- }
- int Union(int u,int v)
- {
- int a=find(u);
- int b=find(v);
- 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;
-
- }