poj 1330 【最近公共祖先问题+fa[]数组+ 节点层次搜索标记】

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#define N 10000+10

using namespace std;

vector<int>a[N];
int fa[N];//记录每个节点的父亲节点
int r[N];//记录每个节点所在的层次

void dfs(int u, int dep)
{       //通过先根遍历计算每个节点的层次
    r[u]=dep;
    vector<int>::iterator it;
    for(it=a[u].begin(); it!=a[u].end(); it++)
    {
        dfs(*it, dep+1);
    }
}

int main()
{
    int tg; scanf("%d", &tg);
    int i, j, k;
    int n, u, v;

    while(tg--)
    {
        scanf("%d", &n);
        for(i=1; i<=n; i++){
            a[i].clear();
            fa[i]=i;//自己是自己的父亲节点
        }

        for(i=0; i<n-1; i++){
            scanf("%d %d", &u, &v);
            a[u].push_back(v);
            fa[v]=u; //u是v的父亲
        }
        for(i=1; i<=n; i++)
            if(fa[i]==i) break;//找到根节点
        dfs(i, 0); //计算每个节点的层次
        int x, y;//寻找x y的最近公共祖先
        scanf("%d %d", &x, &y);
        while(x!=y)
        {
            if(r[x]>r[y]) x=fa[x];//说明x的辈分比y小 将x的父亲搬过来
            else y=fa[y];
        }
        printf("%d\n", x);
    }
    return 0;
}