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


          主站蜘蛛池模板: 本溪市| 瓮安县| 喀喇沁旗| 海丰县| 柘荣县| 涿鹿县| 东乡县| 乡宁县| 马山县| 曲水县| 峨边| 碌曲县| 吴堡县| 长阳| 江川县| 栾城县| 江孜县| 阳朔县| 洪泽县| 塘沽区| 桐梓县| 祁阳县| 繁昌县| 靖州| 卢氏县| 平安县| 微山县| 葵青区| 鄢陵县| 二手房| 淮北市| 黔江区| 湟中县| 阿城市| 宜宾县| 哈巴河县| 五台县| 浦东新区| 莆田市| 延吉市| 宜宾县|