最近公共祖先 boj1278

最近公共祖先Submit: 543   Accepted:182Time Limit: 1000MS  Memory Limit: 65536KDescription
给定一棵树，我们定义树中两个节点A、B的最近公共祖先C为：
1、C既在A到根的路径上，又在B到根的路径上。
2、C离根的距离最远。
如下图：


节点4、5的最近公共祖先是8；节点9、6的最近公共祖先是8；节点7、11的最近公共祖先是4。


Input
输入包含多组测试数据。
首先第一行输入一个数T(T<=20)，表示总共有T组测试数据。
接下来是每组测试数据，第一行是一个数N(N<=200)，表示树中一共有N个点。接下来N-1行，每行两个数A、B，表示A是B的父亲。
然后是一个数M(M<=1000)，表示一共有M个查询，接下来每个查询有两个数A、B，表示询问A和B的最近公共祖先。


Output
首先，输出Case #X：其中X代表是第X组数据(具体格式参照样例)。
然后对每次查询，输出A和B的最近公共祖先。


Sample Input

2
2
1 2
1
1 2
3
1 2
1 3
2
1 2
2 3


Sample Output

Case #1:
1
Case #2:
1
1


代码比较好理解，见注释

#include <stdio.h>
#include <string.h>

int parent[201];
int flag[201];

/* 找到father节点往上的所有祖先节点，并在flag[]数组中标记该节点已访问 */
void find_root(int father)
{
    flag[father] = 1;
    if (parent[father] == -1)
        return ;
    find_root(parent[father]);
}

/* 从father节点开始往上查找，遇到第一个flag[]被标记的节点，就是最近公共祖先 */
int find_common_ancient(int father)
{
    if (1 == flag[father])
        return father;
    return find_common_ancient(parent[father]);
}

int main(int argc, char *argv[])
{
    int T, N, M, father, child, a, b, I, J;
    scanf("%d", &T);
    for (J=0 ; J<T ; J++)
    {
        memset(parent, -1, sizeof(int) * 201);
        scanf("%d", &N);
        for (I=0 ; I<N-1 ; I++)
        {
            scanf("%d %d", &father, &child);
            parent[child] = father;
        }
        printf("Case #%d:", J + 1);
        scanf("%d", &M);
        for (I=0 ; I<M ; I++)
        {
            scanf("%d %d", &a, &b);
            memset(flag, 0, sizeof(int) * 201);
            find_root(a);
            printf("%d
", find_common_ancient(b));
        }
    }
}