POJ 1330 Nearest Common Ancestors 解题报告

时间：2010-05-23 来源：华南理工大学

一、问题描述

http://acm.pku.edu.cn/JudgeOnline/problem?id=1330

二、解题思路

增加一个数组保存每个节点的父节点，然后寻找两个节点到要节点的路径，两条路径第一个相同的节点为最短公共祖先。

三、代码

#include<iostream>
#include<vector>
using namespace std;
int cld[10005];
int prt[10005];
bool b[10005];
bool bf[10005];
int s[10005];
int N,NQ;//节点树和查询数
int Find(int u,int v)
{
    if(u==v)
        return u;
    memset(bf,0,sizeof(bf));
    do
    {
        bf[u]=true;
        u=prt[u];
    }while(prt[u]!=u);
    bf[u]=true;
    while(1)
    {
        if(bf[ v ]==true)
            return v;
        else
            v=prt[v];

    }
}
int main()
{

    int i;
    int u,v;
    int c;
    int pt,cl;
    scanf("%d",&c);
    while(c>0)
    {
        c--;
        scanf("%d",&N);
        memset(b,0,sizeof(b));
        for(i=0;i<N-1;++i)
        {

            scanf("%d%d",&pt,&cl);
            cld[pt]=cl;
            prt[cl]=pt;
            b[cl]=true;
        }
        scanf("%d%d",&u,&v);
        //查找根节点

        for(i=1;i<=N;++i)
        {
            if(b[i]==false)
                break;
        }
        prt[i]=i;//根
        printf("%d\n",Find(u,v));
    }
    return 0;
}