LCA，Tarjan——POJ1330

题目链接

题目含义

建树，求两个数的最近公共祖宗

题目分析

LCA入门模板题，还有一个树上倍增法不会

所以就只用Tarjan算法了

题目代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=1e4+7;
int n,t,tot,a,b;
int head[maxn],f[maxn];
bool vis[maxn],root[maxn];
struct node{
    int to,next;
}edge[maxn*2];
void add(int u,int v){
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}
int get(int x){
    if(f[x]==x)return x;
    else return f[x]=get(f[x]);
}
void dfs(int u,int fa){
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa)continue;
        dfs(v,u);f[v]=u;///要等到回溯完了之后再把子树合并到父节点
    }
    if(u==a&&vis[b])printf("%d
",get(b));
    else if(u==b&&vis[a])printf("%d
",get(a));
    vis[u]=true;
}
int main(){
    scanf("%d",&t);
    while(t--){
        tot=0;
        memset(head,-1,sizeof(head));
        memset(vis,false,sizeof(vis));
        memset(root,true,sizeof(root));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            f[i]=i;
        for(int i=1;i<n;i++){
            scanf("%d%d",&a,&b);
            add(a,b);
            root[b]=false;
        }
        scanf("%d%d",&a,&b);
        for(int i=1;i<=n;i++)
            if(root[i]){dfs(i,0);break;}
    }
    return 0;
}