本文主要是介绍【LCA】求最近公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法一：在线算法 倍增
POJ1330 模板题
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define maxn 10010int point[maxn*2],next[maxn*2],last[maxn],tot,dep[maxn];
int fa[maxn][20],T,n,root,a,b;
bool flag[maxn];void add(int x,int y){point[++tot]=y;next[tot]=last[x];last[x]=tot;}void clear(){memset(flag,true,sizeof(flag));tot=0;memset(last,0,sizeof(last));}void bfs(int root)
{queue<int>q;dep[root]=1;q.push(root);int i,j;while (!q.empty()){int tmp=q.front();q.pop();for (i=last[tmp];i;i=next[i]){int v=point[i];if (v==fa[tmp][0]) continue;dep[v]=dep[tmp]+1;fa[v][0]=tmp;q.push(v);}for (i=fa[tmp][0],j=0;i;i=fa[j][j++])fa[tmp][j+1]=fa[j][j];}} int LCA(int u,int v)
{if (dep[u]<dep[v]) swap(u,v);int i;while (dep[u]>dep[v]){for (i=0;dep[fa[u][i]]>=dep[v];i++);u=fa[u][i-1];}while (u!=v){for (i=1;fa[u][i]!=fa[v][i];i++);u=fa[u][i-1];v=fa[v][i-1];}return u;
}int main()
{ scanf("%d",&T);while (T--){clear();scanf("%d",&n);for (int i=1;i<n;i++){scanf("%d%d",&a,&b);add(a,b);add(b,a);flag[b]=false;}for (int i=1;i<=n;i++)if (flag[i]){root=i;break;}bfs(root);int u,v;scanf("%d%d",&u,&v);printf("%d\n",LCA(u,v));}
}这篇关于【LCA】求最近公共祖先的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
