解题思路

1.判断是否为连通图,使用并查集.在输入的时候将每个结点看成单独的连通分量.每输入一条边相当于连接俩个连通分量.观察输入完所以边时连通分量的个数即可判断整个图是否存在分量.
2.dfs暴力枚举以每个结点为根节点时的最大深度,并记录.

下面给出邻接表存储,与邻接矩阵存储(核心方法都是一样的).邻接矩阵存储在这里会报TLE但是去pat官网能过,哭死.

邻接表

#include<bits/stdc++.h>
using namespace std;

const int N = 10010, M = N * 2;

int h[N], e[M], ne[M], idx;
int p[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx, idx ++ ;
}

int dfs(int u, int father) {
    int depth = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == father) continue;
        depth = max(depth, dfs(j, u) + 1);
    }
    return depth;
}

int main() {
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    int k = n;
    for (int i = 0; i < n - 1; i ++ ) {
        int a, b;
        cin >> a >> b;
        if (find(a) != find(b)) {
            k -- ;
            p[find(a)] = find(b);
        }
        add(a, b), add(b, a);
    }

    if (k > 1) printf("Error: %d components", k);
    else {
        vector<int> nodes;
        int max_depth = -1;

        for (int i = 1; i <= n; i ++ ) {
            int depth = dfs(i, -1);
            if (depth > max_depth) {
                max_depth = dfs(i, -1);
                nodes.clear();
                nodes.push_back(i);
            }else if (max_depth == depth){
                nodes.push_back(i);
            }
        }
        for (int i = 0; i < nodes.size(); i ++ ) cout << nodes[i] << endl;
    }

    return  0;
}

邻接矩阵

#include<bits/stdc++.h>
using namespace std;

const int N = 10010, M = N * 2;

vector<int> g[N];
int p[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}



int dfs(int u, int father) {
    int depth = 0;
    for (auto& t : g[u]) {
        if (t == father) continue;
        depth = max(depth, dfs(t, u) + 1);
    }
    return depth;
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    int k = n;
    for (int i = 0; i < n - 1; i ++ ) {
        int a, b;
        cin >> a >> b;
        if (find(a) != find(b)) {
            k -- ;
            p[find(a)] = find(b);
        }
        g[a].push_back(b);
        g[b].push_back(a);
    }

    if (k > 1) printf("Error: %d components", k);
    else {
        vector<int> nodes;
        int max_depth = -1;

        for (int i = 1; i <= n; i ++ ) {
            int depth = dfs(i, -1);
            if (depth > max_depth) {
                max_depth = dfs(i, -1);
                nodes.clear();
                nodes.push_back(i);
            }else if (max_depth == depth){
                nodes.push_back(i);
            }
        }
        for (int i = 0; i < nodes.size(); i ++ ) cout << nodes[i] << endl;
    }

    return  0;
}