一、定義與定理
LCA：Least Common Ancestors（最近公共祖先），對于一棵有根樹T的任意兩個節(jié)點(diǎn)u，v，求出LCA(T, u, v)，即離跟最遠(yuǎn)的節(jié)點(diǎn)x，使得x同時是u和v的祖先。
在線算法：用比較長的時間做預(yù)處理，但是等信息充足以后每次回答詢問只需要用比較少的時間。
離線算法：先把所有的詢問讀入，然后一起把所有詢問回答完成。
RMQ：給出一個數(shù)組A，回答詢問RMQ(A, i, j)，即A[i...j]之間的最值的下標(biāo)。
二、DFS+RMQ
1）Sparse Table（ST）算法
描述：
1 //初始化
2 INIT_RMQ
3 //max[i][j]中存的是重j開始的i個數(shù)據(jù)中的最大值，最小值類似，num中存有數(shù)組的值
4 for i : 1 to n
5 max[0][i] = num[i]
6 for i : 1 to log(n)/log(2)
7 for j : 1 to n
8 max[i][j] = MAX(max[i-1][j], max[i-1][j+2^(i-1)]
9 //查詢
10 RMQ(i, j)
11 k = log(j-i+1) / log(2)
12 return MAX(max[k][i], max[k][j-2^k+1])
分析：初始化過程實(shí)際上是一個動態(tài)規(guī)劃的思想。易知，初始化過程效率是O(nlogn)，而查詢過程效率是O(1)。ST是一個在線算法。
示例：POJ 3368 解題報告
2）求解LCA問題
描述：
（1）DFS：從樹T的根開始，進(jìn)行深度優(yōu)先遍歷，并記錄下每次到達(dá)的頂點(diǎn)。第一個的結(jié)點(diǎn)是root(T)，每經(jīng)過一條邊都記錄它的端點(diǎn)。由于每條邊恰好經(jīng)過2次，因此一共記錄了2n-1個結(jié)點(diǎn)，用E[1, ... , 2n-1]來表示。
（2）計算R：用R[i]表示E數(shù)組中第一個值為i的元素下標(biāo)，即如果R[u] < R[v]時，DFS訪問的順序是E[R[u], R[u]+1, ..., R[v]]。雖然其中包含u的后代，但深度最小的還是u與v的公共祖先。
（3）RMQ：當(dāng)R[u] ≥ R[v]時，LCA[T, u, v] = RMQ(L, R[v], R[u])；否則LCA[T, u, v] = RMQ(L, R[u], R[v])，計算RMQ。
由于RMQ中使用的ST算法是在線算法，所以這個算法也是在線算法。
示例：ZOJ 3195 解題報告。
三、Tarjan算法
描述：Tarjan算法是一個離線算法，也就是說只有先獲得所有的查詢，再按一個特定的順序進(jìn)行運(yùn)算。
1 //parent為并查集，F(xiàn)IND為并查集的查找操作
2 Tarjan(u)
3 visit[u] = true
4 for each (u, v) in QUERY
5 if visit[v]
6 ans(u, v) = FIND(v)
7 for each (u, v) in TREE
8 if !visit[v]
9 Tarjan(v)
10 parent[v] = u
示例：HDOJ 2586 解題報告。
posted on 2009-07-04 15:25
Icyflame 閱讀(6965)
評論(0) 編輯 收藏 引用 所屬分類:
圖論