Posted on 2007-07-14 13:24
ZelluX 閱讀(478)
評論(0) 編輯 收藏 所屬分類:
Algorithm
PKU1330，普通樹的LCA問題。把結(jié)點A的所有父結(jié)點都保存在一個hash數(shù)組中，然后從結(jié)點B開始向上搜索，直到發(fā)現(xiàn)hash數(shù)組中存在的元素為止。
#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;
}