【PAT_1021】Deepest Root

题目描述：

连通非循环的图可以被认为是树。 树的高度取决于所选的根。 现在你应该找到导致最高树的根。 这样的根被称为最深的根。

输入：

每个输入文件包含一个测试用例。 对于每种情况，第一行包含正整数N（<= 10000），这是节点的数量，因此节点从1到N编号。然后N-1行跟随，每个都描述边缘给定两个 相邻节点的数字。

输出：

对于每个测试用例，在一行中打印每个最深的根。 如果这样的根不是唯一的，则按照其数字的递增顺序打印它们。 如果给定的图形不是树，则打印“Error：K components”，其中K是图中连接组件的数量。

解题思路：

实际上是n个节点之间的边能否构成一棵树，如果不能构成树输出连通分量的个数，能构成则得到构成最深树的高度并输出树的根节点，如果有多个就按从小到大的顺序输出。
所以本题可以先通过dfs判断连通分量的个数，如果只有一个，然后再近些n词dfs得到拥有最高高度的节点。

代码

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool mark[10010];
int maxheigh = 0, resmax = 0;;
void dfs(vector<vector<int> >&graph, vector<int>&res,int start,int cur,int height) {
        mark[cur] = true;
        height++;
        if (graph[cur].size() == 1&& mark[graph[cur][0]]) {
            if (height > maxheigh) {
                maxheigh = height;
            }else if (height == maxheigh) {
                maxheigh = height;
            }
        }
        else {
            for (int i = 0; i < graph[cur].size(); i++) {
                if (!mark[graph[cur][i]]) {
                    dfs(graph, res,start, graph[cur][i],height);
                };
            }
        }
}
int main() {
        int n,a,b;
        cin >> n;
        vector<int>res;
        vector<vector<int> >graph(n + 1);
    fill(mark, mark + 10010, false);
        for (int i = 1; i < n; i++) {
            cin >> a >> b;
            graph[a].push_back(b);
            graph[b].push_back(a);
            
        }
        int components = 0;
        for (int i = 1; i <= n; i++) {
            if (!mark[i]) {
                dfs(graph, res,i,i,0);
                components++;
            }
        }
        if (components > 1) {
            printf("Error: %d components", components);
        }
        else {
            for (int i = 1; i <= n; i++) {
            fill(mark, mark + 10010, false);
                maxheigh = 0;
                dfs(graph, res, i, i, 0);
                if (maxheigh > resmax) {
                    res.clear();
                    res.push_back(i);
                    resmax = maxheigh;
                }   else if (resmax == maxheigh) {
                    resmax = maxheigh;
                    res.push_back(i);
                }
            }
            sort(res.begin(), res.end());
            for (int i = 0; i < res.size(); i++) {
                cout << res[i] << endl;
            }
        }
        return 0;
}