LCA_Tarjan最近公共祖先问题LCA(Least Common Ancestors)问题是这样一个问题
给定有向无环图(就是树,不一定有没有根),给定点U,V,找出点R,保证点R是U,V的公共祖先,且深度最深;或者理解为R离这两个点的距离之和最小.如何找出R呢？
最一般的算法是DFS(DFS本是深度优先搜索,在这里姑且把深度优先遍历也叫做DFS,其实是一种不严谨的说法).先看一道赤裸裸的LCA:POJ 1330 Nearest Common Ancestors 这道题给出了根节点,还保证”the first integer is the parent node of the second integer”(输入第一个数是第二个数的祖先),这是赤裸裸的LCA,算法很简单,从根节点DFS一遍,按DFS层数k给每个节点标上深度deep[i]=k.然后从U点DFS到V点,找到后回溯,在回溯的路径上找到一个deep[i]最小的节点即为LCA.
强大的LCA Tarjan算法能在一遍遍历后应答全部的LCA查询,时间复杂的约为\(\Theta (N)\)
有人说POJ1330是一道LCA Tarjan,在我看来完全不是,LCA Tarjan算法的用途是处理大量请求,如果只有几个(POJ1330每个Case只有一个)询问大可不必写Tarjan算法,不过,1986的编程难度高,如果只是想先学LCA Tarjan, 用1330验证正确性也不是不可以.
LCA Tarjan算法
再来看一道题:POJ1986 Distance Queries 这道题才是真正的LCA Tarjan,只给一个有向无环图,有海量询问;(注意,输入格式与POJ 1984 Navigation Nightmare 一样,需要参考1984的输入格式)
输入格式大意:
- 第1行：节点数N,边数M
- 第2…M+1行：起始节点,目标节点,路径长度,方向(无意义字符,本题直接忽略)
- 第M+2行:询问个数K(1 <= K <= 10,000)
- 第N+3…2+M+K行:查询 U,V
这道题用DFS做的时间复杂度为\(\Theta (K \times N) \) 显然很不理想,这个时候伟大的Tarjan来了,问题迎刃而解.
首先,LCA Tarjan 是一种离线算法,要求一次读入所有询问,一次性输出,这正是LCA Tarjan 算法的精髓
以下大量引用Sideman神牛的话：
LCA Tarjan基本框架：
- 先用随便一种数据结构(链表就行),把关于某个点的所有询问标在节点上,保证遍历到一个点,能得到所有有关这个节点LCA 查询
- 建立并查集.注意:这个并查集只可以把叶子节点并到根节点,即getf(x)得到的总是x的祖先
- 深度优先遍历整棵树,用一个Visited数组标记遍历过的节点,每遍历到一个节点将Visite[i]设成True 处理关于这个节点(不妨设为A)的询问,若另一节点(设为B)的Visited[B]==True,则回应这个询问,这个询问的结果就是getf(B). 否则什么都不做
- 当A所有子树都已经遍历过之后,将这个节点用并查集并到他的父节点(其实这一步应该说当叶子节点回溯回来之后将叶子节点并到自己,并DFS另一子树)
- 当一颗子树遍历完时,这棵子树的内部查询(即LCA在这棵子树内部)都已经处理了
LCA Tarjan 算法演示
假设我们要查询
(3,4) (3,5) (5,6) (6,7) (1,8)
方法见右
以(3,4)为例,说下Tarjan是如何工作的:
当DFS到3时,发现查询(3,4),查看4是否被DFS过,显然这是不可能的.
回溯到2,将3并入2.
DFS节点4,发现查询(3,4),查看visited[3],发现被访问过,应答查询(3,4),应答getf(3)=2;
LCA Tarjan 算法遍历每个点一遍,处理所有询问,时间复杂度为\(\Theta(N+2M) \)
下面贴出POJ1986的题解
首先LCA Tarjan 没的说,但是题目要求回应的不是LCA,而是两节点间距离,可以这样做
- 改造并查集,定义dis[i]数组,保存i到getf(i)的距离
- 定义Deep[i]数组,表示i节点的深度,DFS时顺便更新depp[i];
- 定义Sum[I]数组,表示从根节点到I深度节点的距离.因为在LCA Tarjan算法中 ,LCA(设为X) 必然在DFS路径上,所以X到I的距离为sum[deep[I]]-sum[Deep[X]]
- 响应时,返回值为：dis[A]+sum[deep[getf(A)]]-sum[Deep[B]];
贴之代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#include <iostream> #include <cstring> #include <cstdio> using namespace std; struct link{//链表结构体;目标,长度 ,下一个 int t,l,next; }; struct node_request{//node request int ind,t; int next; }; //Map int lhead[40005];//邻接表头指针 link lin[100000];//链表(无向图) //Tarjan int rhead[40005]; node_request nqs[100000];//链表(请求) int sum[40005],level[40005];//类似栈的部分和(被DFS更新),深度 int f[40005];//并查集 int dis[40005];//Distance about Root int ans[40005]; int visited[40005]; //Other int N,M,K; //Sub int getf(int x); inline void add(int x,int y);//Add X to Y void DFS(int x,int k);//节点,层数 int main(){ int i,j; int fr,t,l; int R=0;//链表尾指针 char rubbish; scanf ("%d%d",&N,&M); lin[0].next=0; memset(lhead,0,sizeof(lhead)); for (i=1;i<=M;i++) {//读入 scanf ("%d%d%d %c",&fr,&t,&l,&rubbish); R++; lin[R].next=lhead[fr]; lin[R].t=t; lin[R].l=l; lhead[fr]=R; R++; lin[R].next=lhead[t]; lin[R].t=fr; lin[R].l=l; lhead[t]=R; } //Finish Build Map ... //Begin Read Request ... scanf("%d",&K); R=0; memset(rhead,0,sizeof(rhead)); for (i=1;i<=K;i++){ scanf("%d%d",&fr,&t); if (fr==t){ ans[i]=0; continue; } R++; nqs[R].ind=i; nqs[R].t=t; nqs[R].next=rhead[fr]; rhead[fr]=R; R++; nqs[R].ind=i; nqs[R].t=fr; nqs[R].next=rhead[t]; rhead[t]=R; } //End reading... for (i=1;i<=N;i++){ f[i]=i; } memset(dis,0,sizeof(dis)); memset(visited,0,sizeof(visited)); //Begin DFS(1,1); for (i=1;i<=K;i++)//按顺序输出结果 printf("%d\n",ans[i]); system("pause"); } int getf(int x){ if (f[x]==x)return x; int ret=getf(f[x]);//最终祖先 dis[x]+=dis[f[x]];//x到祖先的距离=x到f[x]的距离+f[x]到祖先的距离 return f[x]=ret; } inline void add(int x,int y){ //这里的并查集并不需要getf if (getf(x)==getf(y))return ; f[x]=y; } void DFS(int x,int k){//Tarjan 算法主函数 level[x]=k; int i; //处理请求 i=rhead[x];//从链表里读请求 while (i!=0){ if (visited[nqs[i].t]){ //printf("Get visited node %4d \n",nqs[i].t); getf(nqs[i].t);//做路径压缩； 然后就可以开心的使f[x]而不是getf(x)了 //printf("Request to %d ,target is %4d away from its Root(%4d )\n",nqs[i].t,dis[nqs[i].t],f[nqs[i].t]); ans[nqs[i].ind]=dis[nqs[i].t]+sum[k]-sum[level[getf(nqs[i].t)]]; } i=nqs[i].next; } visited[x]=1; //扩展 i=lhead[x]; while (i!=0){ if (!visited[lin[i].t]){ sum[k+1]=sum[k]+lin[i].l; DFS(lin[i].t,k+1);//DFS f[lin[i].t]=x;//归入并查集 dis[lin[i].t]=lin[i].l; } i=lin[i].next; } } |
原创文章，转载请注明： 转载自Comzyh的博客
讲解的真好，真心佩服，多谢博主。
讲解的真好，真心佩服，多谢博主。