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

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

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

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

样例输入：

样例输出：

1
1

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

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 #include <iostream>
 5 using namespace std;
 6 
 7 vector<int>tree[1000002];
 8 int n;
 9 int visit[1000002];
10 int maxP, maxDepth;
11 
12 void dfs(int m, int dept) {
13     if(maxDepth < dept) {
14         maxDepth = dept;
15         maxP = m;
16     }
17     int sizem = tree[m].size();
18     for(int i = 0; i < sizem; i++) {
19         int j = tree[m][i];
20         if(visit[j] == 0) {
21             visit[j] = 1;
22             dfs(j, dept+1);
23             visit[j] = 0;
24         }
25     }
26 }
27 int main(int argc, char const *argv[])
28 {
29     //freopen("input.txt","r",stdin);
30     while(scanf("%d",&n) != EOF) {
31          for(int i = 0; i < n; i++) {
32             tree[i].clear();
33          }
34          int a, b;
35          n--;
36          while(n--) {
37             scanf("%d %d",&a, &b);
38             tree[a].push_back(b);
39             tree[b].push_back(a); 
40          }
41          memset(visit, 0, sizeof(visit));
42          maxP = 0, maxDepth = 0;
43          visit[0] = 1;
44          dfs(0, 0);
45 
46          memset(visit, 0, sizeof(visit));
47          maxDepth = 0;
48          visit[maxP] = 1;
49          dfs(maxP, 0);
50 
51          int ans = (maxDepth + 1)/2;
52          printf("%d
",ans);
53 
54     }   
55     return 0;
56 }

bfs代码如下

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 #include <iostream>
 5 #include <queue>
 6 using namespace std;
 7 
 8 vector<int> tree[1000002];
 9 queue<int> treeq;
10 int n;
11 int visit[1000002];
12 int depth[1000002];
13 
14 int maxP, maxDepth;
15 
16 void bfs() {
17     while(!treeq.empty()) {
18         int p = treeq.front();
19         treeq.pop();
20         
21         int sizep = tree[p].size();
22         for(int i = 0; i < sizep; i++) {
23             int j = tree[p][i];
24             if(visit[j] == 0) {
25                 visit[j] = 1;
26                 depth[j] = depth[p] + 1;
27                 if(maxDepth < depth[j]) {
28                     maxDepth = depth[j];
29                     maxP = j;
30                 }
31                 treeq.push(j);
32             }
33         }
34     }
35 }
36 
37 int main(int argc, char const *argv[])
38 {
39     //freopen("input.txt","r",stdin);
40     while(scanf("%d",&n) != EOF) {
41          for(int i = 0; i < n; i++) {
42             tree[i].clear();
43          }
44          int a, b;
45          n--;
46          while(n--) {
47             scanf("%d %d",&a, &b);
48             tree[a].push_back(b);
49             tree[b].push_back(a); 
50          }
51          memset(visit, 0, sizeof(visit));
52          maxP = 0, maxDepth = 0;
53 
54          treeq.push(0);
55          visit[0] = 1;
56          depth[0] = 0;
57          bfs();
58 
59          memset(visit, 0, sizeof(visit));
60          maxDepth = 0;
61          treeq.push(maxP);
62          visit[maxP] = 1;
63          depth[maxP] = 0;
64          bfs();
65 
66          int ans = (maxDepth + 1)/2;
67          printf("%d
",ans);
68 
69     }   
70     return 0;
71 }