1 条题解

  • 0
    @ 2026-2-17 21:56:15
    #include<bits/stdc++.h>
    using namespace std;
    
    const int MAXN = 1e5 + 10; // 题目n≤1e5,预留足够空间
    vector<int> g[MAXN];       // 邻接表,存储树的无向边
    int n;                      // 树的总结点数
    int dist[MAXN];             // 记录结点到起点的距离
    int pre[MAXN];              // 记录结点的前驱,用于还原直径路径
    
    // [1] BFS函数:从起点start出发,返回离起点最远的结点编号
    int bfs(int start)
    {
        memset(dist, -1, sizeof(dist)); // 距离初始化为-1,表示未访问
        memset(pre, -1, sizeof(pre));   // 前驱初始化为-1
        queue<int> q;
        q.push(start);
        dist[start] = 0; // 起点到自身的距离为0
    
        // 标准BFS遍历整棵树
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            // 遍历当前结点的所有邻接结点
            for(int v : g[u])
            {
                if(dist[v] == -1) // 未访问过的结点
                {
                    dist[v] = dist[u] + 1; // 距离+1
                    pre[v] = u;             // 记录前驱结点,用于后续还原路径
                    q.push(v);
                }
            }
        }
    
        // 找到距离起点最远的结点
        int max_dist = -1, far_node = start;
        for(int i = 1; i <= n; i++)
        {
            if(dist[i] > max_dist)
            {
                max_dist = dist[i];
                far_node = i;
            }
        }
        return far_node;
    }
    
    int main()
    {
        // [2] 输入总结点数
        cin >> n;
        // [3] 输入n-1条无向边,构建邻接表
        for(int i = 1; i <= n-1; i++)
        {
            int x, y;
            cin >> x >> y;
            g[x].push_back(y);
            g[y].push_back(x); // 无向边双向存储
        }
    
        // [4] 第一次BFS:找到直径的第一个端点u
        int u = bfs(1);
        // [5] 第二次BFS:找到直径的第二个端点v,同时得到直径长度L
        int v = bfs(u);
        int L = dist[v]; // 直径的边数长度
    
        // [6] 从v回溯到u,还原直径的完整路径
        vector<int> path;
        for(int cur = v; cur != -1; cur = pre[cur])
        {
            path.push_back(cur);
        }
    
        // [7] 根据直径长度,找到中心结点
        vector<int> center;
        if(L % 2 == 0)
        {
            // 直径长度为偶数,只有1个中心
            center.push_back(path[L/2]);
        }
        else
        {
            // 直径长度为奇数,有2个相邻的中心
            center.push_back(path[L/2]);
            center.push_back(path[L/2 + 1]);
        }
    
        // [8] 按从小到大排序后,输出中心结点
        sort(center.begin(), center.end());
        for(int i = 0; i < center.size(); i++)
        {
            if(i > 0) cout << " ";
            cout << center[i];
        }
        cout << endl;
    
        return 0;
    }
    
    • 1

    信息

    ID
    1082
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者