最近公共祖先
最近公共祖先的問題已經在前面的部落格有說過了。
要看代碼的，本篇部落格寫的是普通樹的最近公共祖先，并不是二叉樹，也許有時間我會寫一下
線上算法
思想
對樹進行dfs（也就是先序周遊），在周遊過程中，記錄下周遊的順序，這裡要注意的是，周遊要記錄下所有路徑，包括節點的第二次通路，或第三次通路。然後這樣就是一個數組了。
0
/ \
1 2
/|\ \
3 4 5 6
/\
7 8
例如上面這棵樹，dfs的順序是：
0 1 3 1 4 7 4 8 4 1 5 1 0 2 6 2 0
在dfs周遊的過程中，記錄下每個節點在樹中的深度以及每個節點在周遊序列第一次出現的位置。
例如以上節點深度數組如下：
而每個節點第一次出現在周遊序列的位置數組如下：
pos :
假如我們要找節點5 和 7 的祖先就下看這兩個節點第一次出現的位置
pos[5] = 10; pos[7] = 5;
這樣在5 - 10之間的周遊序列為：
7 4 8 4 1 5
從這裡面找到深度最小的節點，在一個數組區間找最小值使用的是RMQ-ST算法( 我上兩篇部落格: RMQ-ST算法傳送門 )。找到了之後，就可以進行輸出了！
代碼實作
這裡是用Hihocoder 1069 題目做例子寫的代碼。
//
// main.cpp
// HiHocoder
//
// Created by Alps on 16/5/9.
// Copyright © 2016年 chen. All rights reserved.
//
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
vector<int> tree[];
unordered_map<string, int> map;
unordered_map<int, int> nameSet;
static int idx = ;
string names[];
vector<int> orderTree;
int position[] = {};
int depth[] = {};
int curDepth = ;
int step = ;
int minNum[][];
int getId(string name){
if(map.count(name) == ){
map[name] = idx;
names[idx] = name;
idx++;
}
return map[name];
}
void preOrderTree(int node){
orderTree.push_back(node);
if(position[node] == ){
position[node] = (int)orderTree.size()-;
depth[node] = curDepth;
}
curDepth+=;
for(int i = ; i < tree[node].size();i++){
preOrderTree(tree[node][i]);
orderTree.push_back(node);
}
curDepth-=;
}
void RMQ(int num){
for(int j = ; j < ; j++){
for(int i = ; i < num; i++){
if(i+(<<j)- < num){
minNum[i][j] = depth[minNum[i][j-]]<depth[minNum[i+(<<(j-))][j-]]?minNum[i][j-]:minNum[i+(<<(j-))][j-];
}
}
}
}
string findAnce(int id_1, int id_2){
if(id_1 == id_2) return names[id_1];
int first_1 = position[id_1], first_2 = position[id_2];
if(first_1 > first_2) swap(first_1, first_2);
int k = log2(first_2 - first_1 +);
int mn1 = minNum[first_1][k];
int mn2 = minNum[first_2-(<<k)+][k];
if (depth[mn1] < depth[mn2]) {
return names[mn1];
}
return names[mn2];
}
int main(){
int M,N;
cin>>M;
string name_1, name_2;
int id_1, id_2;
for(int i = ; i < M; i++){
cin>>name_1>>name_2;
id_1 = getId(name_1);
id_2 = getId(name_2);
tree[id_1].push_back(id_2);
nameSet[id_2] = id_1;
if(nameSet.count(id_1) == ){
nameSet[id_1] = id_1;
}
}
int root = ;
while(nameSet[root] != root){
root = nameSet[root];
}
preOrderTree(root);
int num = (int)orderTree.size();
for(int i = ; i < num; i++){
minNum[i][] = orderTree[i];
}
RMQ(num);
cin>>N;
for(int i = ; i < N; i++){
cin>>name_1>>name_2;
id_1 = getId(name_1);
id_2 = getId(name_2);
cout<<findAnce(id_1, id_2)<<endl;
}
return ;
}
測試用例：
//關系個數，前面的是父節點後面是孩子
Adam Sam
Sam Joey
Sam Micheal
Adam Kevin
//查詢的組數，兩個節點是一組
Sam Sam
Adam Sam
Micheal Kevin
輸出：
Sam
Adam
Adam
LCA離線算法
也就是Tarjan算法，這個離線算法的意思就是一次能夠處理很多請求的資料，然後一次性傳回。
思想
http://hihocoder.com/problemset/problem/1067 這裡的提示一和提示二有詳細的解釋。
這裡涉及到的除了本身這個算法，還需要知道并查集的算法，我之前的部落格：并查集傳送門
我直接搬運hihocoder上的解釋了:
“别急，你看這個圖——好吧，其實是棵樹，代表着我們這個問題的一個輸入，而這幾個是我們要處理的詢問。”小Hi在準備好的黑闆上寫寫畫畫道。
算法基礎 - 最近公共祖先（線上算法/離線算法）最近公共祖先 “好的。”小Ho點點頭。
“而我現在要做的呢，是以深度優先搜尋的順序來通路這棵樹。”小Hi繼續道：“在這個過程中，我會給這棵樹的結點染色，一開始所有結點都是白色的。而當我第一次經過某個結點的時候，我會将它染成灰色，而當我第二次經過這個結點的時候——也就是離開這棵子樹的時候，我會将它染成黑色。”
“但是這樣做的意義何在呢？”小Ho的問題來了。
“舉個例子，當我們深度優先搜尋到A結點時，我們發現A結點和B結點是我們需要處理的一組詢問。”小Hi在黑闆上畫着。
小Ho點了點頭。
“這個時候，這個圖的染色情況是這樣的。”小Hi順手就塗上了顔色，繼續道：“我們這個時候就要去檢視B結點的顔色——灰色，說明我們進入了以B結點為根的子樹，但是還沒有從這棵子樹中出去，你知道這意味着什麼嗎？”
算法基礎 - 最近公共祖先（線上算法/離線算法）最近公共祖先 “意味着A結點在B結點所在的子樹中——那麼B結點就是A和B結點的最近公共祖先了？”小Ho答道。
“沒錯，但這隻是一種簡單的情況，如果我詢問的不是A和B這兩個結點，而是A和C這兩個結點，那麼在通路到A的時候，C的顔色是黑色的，這時候我該怎麼處理呢？”小Hi繼續問道。
“唔……首先肯定隻能從所有灰色結點中找——這是A結點的所有祖先結點！那麼……就是C結點向上的第一個灰色結點？”小Ho答道。
“是的，但是你這樣做不會和上一次的樸素做法一樣低效率麼？”小Hi反問道。
“的确是的……每次都要向上找會很吃不消的。”小Ho困惑了：“那麼我該怎麼辦呢？”
“先别着急，我們把之前的分情況讨論結束，再來細談這個問題……那麼接下來隻有一種可能了，如果詢問的時A和P這兩個結點，而此時P還是白色的，你覺得怎麼處理比較合适？”小Hi道。
“唔……我覺得把，既然這個時候P還是白色，那麼就先不要管這個詢問了，畢竟現在關于P的資訊一點都不知道。而且反正深度優先搜尋會處理到P結點，那個時候A結點肯定已經不是白色了，就可以沿用之前的方法進行解決了！”小Ho沉思了一會，答道。
“是的！那麼你有沒有發現，這樣一遍處理下來，你就可以求出所有準備好的詢問的結果了——我先計算每個結點涉及到的詢問，然後在深度優先搜尋的過程中對結點染色，如果發現目前通路的結點是涉及到某個詢問，那麼我就看這個詢問中另一個結點的顔色，如果是白色，則留待之後處理，如果是灰色，那麼最近公共祖先必然就是這個灰色結點，如果是黑色，那麼最近公共祖先就是這個黑色結點向上的第一個灰色結點。”小Hi總結道：“而我們唯一剩下的問題，就是怎麼樣快速的找到一個黑色結點向上的第一個灰色結點。算法基礎 - 最近公共祖先（線上算法/離線算法）最近公共祖先
快速找到第一個灰色節點就是使用并查集的思想，首先最開始的時候，每個節點都指向自己，當這個節點周遊它的一個孩子之後，就把這個孩子變成黑色了，然後把這個孩子指向目前節點（目前節點一定是灰色）這樣就能快速找到灰色節點的位置了。
代碼實作
我這個代碼沒辦法AC掉Hihocoder上面的題目，但是我測試了非常多的用例，完全不知道哪裡出錯了，如果有人能看出來哪個用例能夠測試出來錯誤，請私信我，必有重謝！！
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;
struct Edge{
int val;
int id;
Edge(int v, int i): val(v), id(i){}
};
vector<int> tree[];
vector<int> set[];
unordered_map<string, int> names;
unordered_map<int, int> nameSet;
string strs[];
static int id = ;
vector<Edge> query[];
int color[];
int ances[] = {};
int father[] = {};
int getId(string name){
if(names.count(name) == ){
names[name] = id;
strs[id] = name;
id++;
}
return names[name];
}
int findAnce(int val){
if(val == nameSet[val]){
return val;
}
nameSet[val] = findAnce(nameSet[val]);
return nameSet[val];
}
void dfs(int id){
color[id] = ;
if (!query[id].empty()) {
for (int j = ; j < query[id].size(); j++) {
if (ances[query[id][j].id] != ) {
continue;
}
if (color[query[id][j].val] == ) {
int curAnce = findAnce(query[id][j].val);
ances[query[id][j].id] = curAnce;
}
if (color[query[id][j].val] == ) {
ances[query[id][j].id] = query[id][j].val;
}
}
}
for(int i = ; i < tree[id].size(); i++){
int cur = tree[id][i];
dfs(cur);
color[cur] = ;
nameSet[cur] = id;
}
}
int main(){
int M,N;
cin>>M;
string name_1, name_2;
int id_1, id_2;
for(int i = ; i < M; i++){
cin>>name_1>>name_2;
id_1 = getId(name_1);
id_2 = getId(name_2);
tree[id_1].push_back(id_2);
father[id_2] = ;
nameSet[id_1] = id_1;
nameSet[id_1] = id_1;
}
cin>>N;
for(int i = ; i < N; i++){
cin>>name_1>>name_2;
id_1 = getId(name_1);
id_2 = getId(name_2);
query[id_1].push_back(Edge(id_2, i));
query[id_2].push_back(Edge(id_1, i));
}
int ance = ;
for (int i = ; i < M; i++) {
if (father[i] == ) {
ance = i;
break;
}
}
dfs(ance);
for (int i = ; i < N; i++) {
cout<<strs[ances[i]]<<endl;
}
return ;
}
和上面的一樣的測試用例都可以。