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;
          }


          主站蜘蛛池模板: 昭觉县| 平乡县| 福海县| 龙井市| 寻乌县| 区。| 永泰县| 永善县| 漳浦县| 汤原县| 厦门市| 庆元县| 嘉定区| 华蓥市| 翁源县| 宜州市| 永定县| 奉化市| 兴隆县| 新疆| 沛县| 三河市| 喀什市| 资中县| 南康市| 靖远县| 吉木乃县| 利川市| 桦南县| 道孚县| 栾城县| 南宁市| 英吉沙县| 自治县| 奈曼旗| 泌阳县| 类乌齐县| 巴彦淖尔市| 龙州县| 天峻县| 贵南县|