posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

          LCA 最近公共祖先問題 (2)

          Posted on 2007-07-14 13:24 ZelluX 閱讀(480) 評論(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;
          }


          主站蜘蛛池模板: 贵溪市| 东城区| 罗田县| 汾阳市| 丰顺县| 东乌珠穆沁旗| 南华县| 孝感市| 同仁县| 集安市| 甘洛县| 文山县| 保德县| 敖汉旗| 青岛市| 安图县| 嘉善县| 佳木斯市| 黄石市| 上蔡县| 平顶山市| 禹城市| 四子王旗| 翁牛特旗| 喀喇沁旗| 宁蒗| 北流市| 稻城县| 正阳县| 云林县| 武夷山市| 沧源| 普定县| 盱眙县| 尼玛县| 专栏| 蒙阴县| 兴业县| 仁怀市| 长顺县| 墨脱县|