题意：给出一棵树，再给出两个节点a、b，求离它们最近的公共祖先。
方法一：
先用vector存储某节点的子节点，fa数组存储某节点的父节点，最后找出fa[root]=0的根节点root。
之后求每个节点的“高度”，更节点的高度为1，每往下一层高度+1。
读取a和b后，先求出它们位于同一个高度的祖先：
1.若此祖先相同，则即为最近的公共祖先。
2.若不相同，则求各自的父节点，知道两者的父节点相同，即为最近的公共祖先。
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <vector> using namespace std; const int maxn=10010; int n; vector<int> son[maxn]; int depth[maxn]; //depth[i]表示节点i的“高度”，这里根节点高度为1，每往下一层高度+1 int fa[maxn]; //fa[i]表示i的父节点 void init(){ for(int i=0;i<maxn;i++) son[i].clear(); memset(depth,0,sizeof(depth)); memset(fa,0,sizeof(fa)); } //求出每个节点的“高度” void dealdepth(int u){ for(int i=0;i<son[u].size();i++){ int v=son[u][i]; depth[v]=depth[u]+1; dealdepth(v); } return; } int solve(int a,int b){ //depth[a]>depth[b]，表示b在a的上方，先求出a的与b在同一层的祖先 if(depth[a]>depth[b]){ while(depth[a]>depth[b]) a=fa[a]; if(a==b) return a; } //depth[a]<depth[b]，表示a在b的上方，先求出b的与a在同一层的祖先 else if(depth[a]<depth[b]){ while(depth[a]<depth[b]) b=fa[b]; if(a==b) return a; } //同时求祖先，直至相等 while(a!=b){ a=fa[a]; b=fa[b]; } return a; } int main() { int t,a,b,root,u,v; //root:根节点 scanf("%d",&t); while(t--){ init(); scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); son[u].push_back(v); fa[v]=u; } for(int i=1;i<=n;i++){ if(fa[i]==0){ root=i; break; } } depth[root]=1; dealdepth(root); scanf("%d%d",&a,&b); int ans=solve(a,b); printf("%d ",ans); } return 0; }
方法二：用Tarjan算法求
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <string> #include <vector> /* Tarjan算法 */ using namespace std; const int maxn=10001; int n,t,a,b; //a,b是要求公共祖先的两点 bool flag; //flag为true表明LCA已经求出了a,b的公共祖先，那么就不用继续往下求了 int vis[maxn]; //LCA标记哪些节点已被访问过 int indegree[maxn]; //记录每个节点的入度，用来找寻根节点 int head[maxn]; int tot; int ans; struct Edge{ int to,next; }edge[maxn]; void add(int u,int v){ edge[tot].next=head[u]; edge[tot].to=v; head[u]=tot++; } //并查集 struct UF{ int fa[maxn]; void init(){ for(int i=0;i<=n;i++) fa[i]=i; } int find_root(int x){ if(fa[x]!=x) fa[x]=find_root(fa[x]); return fa[x]; } void Union(int u,int v){ fa[v]=fa[u]; } }uf; void LCA(int u){ if(flag) return; int v; for(int k=head[u];k!=-1;k=edge[k].next){ v=edge[k].to; LCA(v); uf.Union(u,v); } vis[u]=1; //标记节点u //看看u是否是查询的两个节点中的一个 if(u==a){ if(vis[b]){ ans=uf.fa[uf.find_root(b)]; flag=true; } } else if(u==b){ if(vis[a]){ ans=uf.fa[uf.find_root(a)]; flag=true; } } } int main() { int root,u,v; cin>>t; while(t--){ memset(indegree,0,sizeof(indegree)); memset(head,-1,sizeof(head)); tot=0; cin>>n; for(int i=1;i<n;i++){ cin>>u>>v; add(u,v); indegree[v]++; } for(int i=1;i<=n;i++){ if(!indegree[i]){ root=i; break; } } cin>>a>>b; flag=false; memset(vis,0,sizeof(vis)); uf.init();//一开始忘记初始化了额 LCA(root); cout<<ans<<endl; } return 0; }