九度oj 题目1536：树的最小高度

题目描述：: 给定一棵无向树，我们选择不同的节点作为根节点时，可以得到不同的高度（即树根节点到叶子节点距离的最大值），现在求这棵树可能的最低高度。

输入：: 输入可能包含多个测试案例。
对于每个测试案例，输入的第一行为一个整数n(1 <= n <= 1000000)。
接下n-1行，每行包括两个整数u,v( 0<= u,v < n)代表这棵树的一个边连接的两个顶点。

输出：: 对应每个测试案例，输出这棵树可能的最小高度。

样例输入：

样例输出：

1

1

这个题技巧性很强，
最小高度为树中两结点最长距离的一半，故关键是求两点间的最长距离
求最长距离时，首先对任一节点进行dfs或bfs，找到其最远距离点，再对此点进行第二次dfs或bfs遍历，得出的距离既是最远距离。
dfs代码如下

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <iostream>

 using namespace std;

 vector<int>tree[];

 int n;

 int visit[];

 int maxP, maxDepth;

 void dfs(int m, int dept) {

     if(maxDepth < dept) {

         maxDepth = dept;

         maxP = m;

     }

     int sizem = tree[m].size();

     for(int i = ; i < sizem; i++) {

         int j = tree[m][i];

         if(visit[j] == ) {

             visit[j] = ;

             dfs(j, dept+);

             visit[j] = ;

         }

     }

 }

 int main(int argc, char const *argv[])

 {

     //freopen("input.txt","r",stdin);

     while(scanf("%d",&n) != EOF) {

          for(int i = ; i < n; i++) {

             tree[i].clear();

          }

          int a, b;

          n--;

          while(n--) {

             scanf("%d %d",&a, &b);

             tree[a].push_back(b);

             tree[b].push_back(a);

          }

          memset(visit, , sizeof(visit));

          maxP = , maxDepth = ;

          visit[] = ;

          dfs(, );

          memset(visit, , sizeof(visit));

          maxDepth = ;

          visit[maxP] = ;

          dfs(maxP, );

          int ans = (maxDepth + )/;

          printf("%d\n",ans);

     }

     return ;

 }

bfs代码如下

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <iostream>

 #include <queue>

 using namespace std;

 vector<int> tree[];

 queue<int> treeq;

 int n;

 int visit[];

 int depth[];

 int maxP, maxDepth;

 void bfs() {

     while(!treeq.empty()) {

         int p = treeq.front();

         treeq.pop();

         int sizep = tree[p].size();

         for(int i = ; i < sizep; i++) {

             int j = tree[p][i];

             if(visit[j] == ) {

                 visit[j] = ;

                 depth[j] = depth[p] + ;

                 if(maxDepth < depth[j]) {

                     maxDepth = depth[j];

                     maxP = j;

                 }

                 treeq.push(j);

             }

         }

     }

 }

 int main(int argc, char const *argv[])

 {

     //freopen("input.txt","r",stdin);

     while(scanf("%d",&n) != EOF) {

          for(int i = ; i < n; i++) {

             tree[i].clear();

          }

          int a, b;

          n--;

          while(n--) {

             scanf("%d %d",&a, &b);

             tree[a].push_back(b);

             tree[b].push_back(a);

          }

          memset(visit, , sizeof(visit));

          maxP = , maxDepth = ;

          treeq.push();

          visit[] = ;

          depth[] = ;

          bfs();

          memset(visit, , sizeof(visit));

          maxDepth = ;

          treeq.push(maxP);

          visit[maxP] = ;

          depth[maxP] = ;

          bfs();

          int ans = (maxDepth + )/;

          printf("%d\n",ans);

     }

     return ;

 }

巴特西

九度oj 题目1536：树的最小高度

最新文章

热门文章