LCA 学习算法 （最近的共同祖先）poj 1330

Nearest Common Ancestors

Description

A rooted tree is a well-known data structure in computer science and engineering. An example is shown below: 

 
In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is. 

For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y. 

Write a program that finds the nearest common ancestor of two distinct nodes in a tree. 

Input

Output

Sample Input

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

Sample Output

4
3

在求解近期公共祖先为问题上，用到的是Tarjan的思想，从根结点開始形成一棵深搜树。处理技巧就是在回溯到结点u的时候。u的子树已经遍历。这时候才把u结点放入合并集合中，这样u结点和全部u的子树中的结点的近期公共祖先就是u了，u和还未遍历的全部u的兄弟结点及子树中的近期公共祖先就是u的父亲结点。

这样我们在对树深度遍历的时候就非常自然的将树中的结点分成若干的集合，两个集合中的所属不同集合的随意一对顶点的公共祖先都是同样的，也就是说这两个集合的近期公共祖先仅仅有一个。时间复杂度为O（n+q），n为节点，q为询问节点对数。

#include"stdio.h"
#include"string.h"
#include"vector"
using namespace std;
#define N 11000
const int inf=1<<20;
vector<int>g[N];
int s,t,n;
int f[N],pre[N],ans[N];
bool vis[N];
int findset(int x)
{
    if(x!=f[x])
        f[x]=findset(f[x]);
    return f[x];
}
int unionset(int a,int b)
{
    int x=findset(a);
    int y=findset(b);
    if(x==y)
        return x;
    f[y]=x;
    return x;
}
void lca(int u)
{
    int i,v;
    ans[u]=u;
    for(i=0;i<g[u].size();i++)
    {
        v=g[u][i];  //訪问由父节点引出的各个子节点
        lca(v);
        int x=unionset(u,v); //把父子节点合并
        ans[x]=u;     //祖先节点记为U
    }
    vis[u]=1;
    if(u==s&&vis[t])  //两个节点依次被訪问标记，第二次訪问时才满足条件
    {
        printf("%d\n",ans[findset(t)]);
        return ;
    }
    else if(u==t&&vis[s])
    {
        printf("%d\n",ans[findset(s)]);
        return ;
    }
}
int main()
{
    int i,u,v,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            pre[i]=-1;    //记录节点I的父节点
            f[i]=i;       //并查集记录根节点
            vis[i]=0;
            g[i].clear();
        }
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            pre[v]=u;
        }
        scanf("%d%d",&s,&t);
        for(i=1;i<=n;i++)
            if(pre[i]==-1)
                break;
        lca(i);
    }
    return 0;
}