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 动画演示
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 ;
}
}
相关
讲解的真好，真心佩服，多谢博主。
讲解的真好，真心佩服，多谢博主。