C语言求树的最大高度：算法与代码实现

在图论中，树是任意两个顶点间有且只有一条路径的图。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。

有一个根的树叫做有根树。

有根树中的节点可以根据到根的距离分层。一棵有根数的层数叫做这棵树的高度。

我们知道，只要确定树根，就可以构造出一棵树。

选取不同的结点当作树根可以构造不同树高的树，你的任务就是选取编号最小的结点，使得以该结点为树根的树的高度最大。

输入：

输入数据的第一行为一个整数N (2<=N<=100,000)，表示树的结点数量，结点编号分别为1，2，3，…，N。之后有N-1行，每行有两个整数A和B，表示A结点和B结点之间有一条边。输入数据保证可以构造出一棵有根树。

有多组测试数据，输入以EOF结束。

输出：

输出两个整数minNode和Hight，表示以编号minNode为树根的树的最大高度为Hight，如果存在多种情况使得高度Hight最大，输出编号最小的minNode。

样例输入：

样例输出：

6 5

思路：

先用 DFS 遍历树，求出每个点为根的子树高度，然后再从这个子树高度数组中找到最大值，最大值对应的下标即为以其为根的子树高度最大的点。注意，如果有多个点的子树高度最大，要输出编号最小的点。

AC Code：

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
vector<int> G[MAXN];
int depth[MAXN];
int maxDepth, minNode;

void dfs(int u, int fa, int d) {
    depth[u] = d;
    if (d > maxDepth) {
        maxDepth = d;
        minNode = u;
    } else if (d == maxDepth && u < minNode) {
        minNode = u;
    }
    for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if (v != fa) {
            dfs(v, u, d + 1);
        }
    }
}

int main() {
    int n, u, v;
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) {
            G[i].clear();
        }
        for (int i = 1; i < n; ++i) {
            scanf("%d %d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        maxDepth = 0;
        minNode = n;
        dfs(1, 0, 1);
        printf("%d %d\n", minNode, maxDepth);
    }
    return 0;
}