LCA 近期公共祖先 小结

以poj 1330为例。对LCA的3种经常使用的算法进行介绍，分别为

1. 离线tarjan

2. 基于倍增法的LCA

3. 基于RMQ的LCA



1. 离线tarjan

/*poj 1330 Nearest Common Ancestors

  题意：

  给出一棵大小为n的树和一个询问(u,v), 问(u,v)的近期公共祖先。

  限制：

  2 <= n <= 10000

  思路：

  离线tarjan

 */

#include<iostream>

#include<cstdio>

#include<vector>

#include<cstring>

using namespace std;

#define PB push_back

const int N=10005;

int fa[N];

vector<int> tree[N],query[N];

int anc[N];	//ancestor

bool vis[N];

int get_fa(int x){

	if(x!=fa[x]) return fa[x]=get_fa(fa[x]);

	return x;

}

void merge(int x,int y){

	int fa_x=get_fa(x);

	int fa_y=get_fa(y);

	if(fa_x==fa_y) return ;

	fa[fa_y]=fa_x;

}

//就是把搜过的合并在一起

void LCA(int rt){

	anc[rt]=rt;

	for(int i=0;i<tree[rt].size();++i){

		int ch=tree[rt][i];

		LCA(ch);

		merge(rt,ch);

		//cout<<rt<<' '<<ch<<' '<<get_fa(ch)<<endl;

		anc[get_fa(ch)]=rt;

	}

	vis[rt]=true;

	for(int i=0;i<query[rt].size();++i){

		if(vis[query[rt][i]]){

			cout<<anc[get_fa(query[rt][i])]<<endl;

			return ;

		}

	}

}

void init(int n){

	memset(vis,0,sizeof(vis));

	memset(anc,0,sizeof(anc));

	for(int i=0;i<=n;++i){

		fa[i]=i;

		tree[i].clear();

		query[i].clear();

	}

}

int indeg[N];

void gao(int n){

	for(int i=1;i<=n;++i){

		if(indeg[i]==0){

			LCA(i);

			break;

		}

	}

}

int main(){

	int T;

	scanf("%d",&T);

	while(T--){

		int n;

		scanf("%d",&n);

		init(n);

		int u,v;

		for(int i=0;i<n-1;++i){

			scanf("%d%d",&u,&v);

			tree[u].PB(v);

			++indeg[v];

		}

		scanf("%d%d",&u,&v);

		query[u].PB(v);

		query[v].PB(u);

		gao(n);

	}

	return 0;

}

2. 基于倍增法的LCA

/*poj 1330 Nearest Common Ancestors

  题意：

  给出一棵大小为n的树和一个询问(u,v), 问(u,v)的近期公共祖先。

  限制：

  2 <= n <= 10000

  思路：

  基于倍增法的算法，

  朴素的算法为：

  假设节点w是u和v的公共祖先的话，首先让u。v中较深的一方向上走|depth(u)-depth(v)|步。然后再一步一步向上走。直到同一个节点

  基于倍增法的优化：

  对于每一个节点预处理出2, 4, 8, ... 2^k步的祖先，然后搞。

 */

#include<iostream>

#include<cstdio>

#include<vector>

#include<cstring>

using namespace std;

#define PB push_back

const int N=100005;

const int LOGN=22;

vector<int> tree[N];

int fa[N][LOGN];

int depth[N];

void dfs(int u,int p,int d){

	depth[u]=d;

	fa[u][0]=p;

	for(int i=0;i<tree[u].size();++i){

		if(tree[u][i]!=p)

			dfs(tree[u][i],u,d+1);

	}

}

int LCA(int u,int v){

	if(depth[u]>depth[v]) swap(u,v);

	for(int i=0;i<LOGN;++i){

		if(((depth[v]-depth[u]) >> i) & 1)

			v=fa[v][i];

	}

	if(u==v) return u;

	for(int i=LOGN-1;i>=0;--i){

		if(fa[u][i]!=fa[v][i]){

			u=fa[u][i];

			v=fa[v][i];

		}

	}

	return fa[u][0];

}

int indeg[N];

void predo(int n){

	int root;

	for(int i=1;i<=n;++i){

		if(!indeg[i]){

			root=i;

			break;

		}

	}

	dfs(root,-1,0);

	for(int j=0;j+1<LOGN;++j){

		for(int i=1;i<=n;++i){

			if(fa[i][j]<0) fa[i][j+1]=-1;

			else fa[i][j+1]=fa[fa[i][j]][j];

		}

	}

}

void init(int n){

	memset(indeg,0,sizeof(indeg));

	for(int i=0;i<=n;++i)

		tree[i].clear();

}

int main(){

	int T;

	scanf("%d",&T);

	while(T--){

		int n;

		scanf("%d",&n);

		init(n);

		int u,v;

		for(int i=0;i<n-1;++i){

			scanf("%d%d",&u,&v);

			tree[u].PB(v);

			++indeg[v];

		}

		predo(n);

		scanf("%d%d",&u,&v);

		printf("%d\n",LCA(u,v));

	}

	return 0;

}

3. 基于RMQ的LCA

/*poj 1330 Nearest Common Ancestors

  题意：

  给出一棵大小为n的树和一个询问(u,v), 问(u,v)的近期公共祖先。

  限制：

  2 <= n <= 10000

  思路：

  对于涉及有根树的问题。将树转化为从根dfs标号后得到的序列处理的技巧经常十分有效。对于LCA。这个技巧也十分有效。首先。按从根dfs訪问的顺序得到顶点序列vs[i]和相应的深度depth[i]，对于每一个顶点v，记其在vs中首次出现的下标为id[v]。

  这些都能够dfs一遍搞定。而LCA(u,v)就是訪问u之后到訪问v之前所经过顶点中离根近期的那个。如果id[u] <= id[v]则有：

  LCA(u,v) = vs[id[u] <= i <= id[v]中令depth(i)最小的i]

  这个能够用rmq求得。

*/

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<vector>

using namespace std;

#define PB push_back

const int N=100005;

int dp[N*2][18];

void make_rmq_index(int n,int b[]){ //返回最小值相应的下标

    for(int i=0;i<n;i++)

        dp[i][0]=i;

    for(int j=1;(1<<j)<=n;j++)

        for(int i=0;i+(1<<j)-1<n;i++)

            dp[i][j]=b[dp[i][j-1]] < b[dp[i+(1<<(j-1))][j-1]]?

dp[i][j-1]:dp[i+(1<<(j-1))][j-1];

}

int rmq_index(int s,int v,int b[]){

	int k=(int)(log((v-s+1)*1.0)/log(2.0));

	return b[dp[s][k]]<b[dp[v-(1<<k)+1][k]]?

dp[s][k]:dp[v-(1<<k)+1][k];

}

vector<int> tree[N];

int vs[N*2]; //dfs訪问的顺序

int depth[N*2]; //节点的深度

int id[N]; //各个顶点在vs中首次出现的下标

void dfs(int u,int p,int d,int &k){

	id[u]=k;

	vs[k]=u;

	depth[k++]=d;

	for(int i=0;i<tree[u].size();++i){

		if(tree[u][i]!=p){

			dfs(tree[u][i],u,d+1,k);

			vs[k]=u;

			depth[k++]=d;

		}

	}

}

int indeg[N];

void predo(int n){

	int root;

	for(int i=1;i<=n;++i){

		if(indeg[i]==0){

			root=i;

			break;

		}

	}

	int k=0;

	dfs(root,-1,0,k);

	/*

	for(int i=0;i<k;++i)

		cout<<i<<':'<<vs[i]<<' ';

	cout<<endl;

	for(int i=0;i<k;++i)

		cout<<i<<':'<<depth[i]<<' ';

	cout<<endl;

	for(int i=1;i<=n;++i)

		cout<<i<<':'<<id[i]<<' ';

	cout<<endl;

	*/

	make_rmq_index(n*2-1,depth);

}

int LCA(int u,int v){

	return vs[rmq_index(min(id[u],id[v]), max(id[u],id[v])+1, depth)];

}

void init(int n){

	memset(indeg,0,sizeof(indeg));

	for(int i=1;i<=n;++i)

		tree[i].clear();

}

int main(){

	int T;

	scanf("%d",&T);

	while(T--){

		int n;

		scanf("%d",&n);

		init(n);

		int u,v;

		for(int i=0;i<n-1;++i){

			scanf("%d%d",&u,&v);

			tree[u].PB(v);

			++indeg[v];

		}

		predo(n);

		scanf("%d%d",&u,&v);

		printf("%d\n",LCA(u,v));

	}

	return 0;

}

/*

input:

1

5

2 3

3 4

3 1

1 5

3 5

output:

0:2 1:3 2:4 3:3 4:1 5:5 6:1 7:3 8:2

0:0 1:1 2:2 3:1 4:2 5:3 6:2 7:1 8:0

1:4 2:0 3:1 4:2 5:5

3

*/