最近公共祖先
最近公共祖先的问题已经在前面的博客有说过了。
要看代码的，本篇博客写的是普通树的最近公共祖先，并不是二叉树，也许有时间我会写一下
在线算法
思想
对树进行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 ;
}
和上面的一样的测试用例都可以。