posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

LCA 最近公共祖先问题 (2)

Posted on 2007-07-14 13:24 ZelluX 阅读(466) 评论(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;
}



只有注册用户登录后才能发表评论。


网站导航: