1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] 全局常量与变量定义 const int MAXN = 1e5 + 10; // 适配题目n≤1e5的规模 vector<int> g[MAXN]; // 邻接表,存储树的无向边 int n; // 树的总结点数 int sz[MAXN]; // sz[u]:以u为根的子树的总结点数 int min_max_block = INT_MAX; // 记录所有结点中,删除后的最大连通块的最小值 vector<int> center; // 存储树的重心结点 // [2] DFS核心函数:计算子树大小,同时求解重心 // 参数说明:u=当前遍历的结点,fa=当前结点的父结点(避免往回走) void dfs(int u, int fa) { sz[u] = 1; // 子树初始大小为当前结点自身 int max_block = 0; // 记录删除当前结点u后,最大的连通块大小 // 遍历当前结点的所有邻接结点 for(int v : g[u]) { if(v == fa) continue; // 跳过父结点,防止死循环 dfs(v, u); // 递归计算子结点的子树大小 sz[u] += sz[v]; // 累加子树大小到当前结点 max_block = max(max_block, sz[v]); // 更新子树中的最大连通块 } // 加上父节点方向的连通块大小,得到删除u后的最大连通块 max_block = max(max_block, n - sz[u]); // [3] 更新重心:如果当前结点的最大连通块更小 if(max_block < min_max_block) { min_max_block = max_block; center.clear(); // 清空之前的重心 center.push_back(u); // 加入当前结点为新的重心 } // 如果和当前最小值相等,说明有多个重心,加入列表 else if(max_block == min_max_block) { center.push_back(u); } } int main() { // 关闭cin同步,加速输入,避免n=1e5时输入超时 ios::sync_with_stdio(false); cin.tie(nullptr); // [4] 输入总结点数 cin >> n; // [5] 输入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); // 无向边双向存储 } // [6] 从结点1开始DFS,根节点的父结点设为-1(不存在的结点) dfs(1, -1); // [7] 按题目要求,将重心从小到大排序 sort(center.begin(), center.end()); // [8] 输出结果 for(int i = 0; i < center.size(); i++) { if(i > 0) cout << " "; cout << center[i]; } cout << endl; return 0; }
- 1
信息
- ID
- 1083
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者