Posted on 2007-07-14 13:24
ZelluX 阅读(475)
评论(0) 编辑 收藏 所属分类:
Algorithm
PKU1330，普通树的LCA问题。把结点A的所有父结点都保存在一个hash数组中，然后从结点B开始向上搜索，直到发现hash数组中存在的元素为止。
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode *pTree;
struct TreeNode
{
int value;
pTree father;
};
main()
{
int cases, n, i;
scanf("%d", &cases);
pTree nodes[10000];
for (i = 0; i < 10000; i++)
{
nodes[i] = malloc(sizeof(struct TreeNode));
nodes[i]->value = i;
}
int flag[10000];
while (cases > 0)
{
cases --;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
nodes[i]->father = NULL;
}
int x, y;
for (i = 0; i < n - 1; i++)
{
scanf("%d %d", &x, &y);
nodes[y - 1]->father = nodes[x - 1];
}
scanf("%d %d", &x, &y);
for (i = 0; i < n - 1; i++)
flag[i] = 0;
pTree p = nodes[x - 1];
while (p != NULL)
{
flag[p->value] = 1;
p = p->father;
}
p = nodes[y - 1];
while (p != NULL)
{
if (flag[p->value])
{
printf("%d\n", p->value + 1);
break;
}
p = p->father;
}
}
return 0;
}