1 条题解
-
0
#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
- 上传者