当前位置：首页 > news >正文

求树的重心

news 2025/7/13 4:14:21

题目：

给定一颗树，树中包含 n个结点和 n−1条无向边。树的重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

思路：

用邻接表存储树，同时用一个数组保存以每个结点为根的子树大小（图中红色框部分），递归DFS遍历树，在回溯阶段计算删除该结点后它所有的子树大小和“上面剩余部分”的大小，取最大的那块记为maxPart，取所有结点中最小的那个maxPart记为minMaxPart，其对应的结点就是树的重心。

代码：

#include<iostream>
#include<vector>
#include<cmath>
#include<climits>
using namespace std;int n;
vector<vector<int>> tree;//邻接表-树
vector<int> subtreeSize; //每个结点作为根的子树大小
int minMaxPart = INT_MAX;
vector<int> centroids;// 所有重心void dfs(int u, int parent)
{subtreeSize[u] = 1;//先把自己算上int maxPart = 0;//最大子块for (int v : tree[u]){//这一步很关键：其实无所谓parent，图也可以这么处理，这个parent其实是递归上一层的那个结点//这么做是为了把邻居结点分成两部分（1）递归上一层的结点（2）接下来要去的那些结点//这样subtreeSIze也才有了意义，它是接下来要去的那些结点“引领”的块的大小if (v == parent) continue;dfs(v, u);subtreeSize[u] += subtreeSize[v];maxPart = max(maxPart, subtreeSize[v]);//寻找最大子块}int upPart = n - subtreeSize[u];//把u作为根节点时，它的父节点那一块也成了一个子块maxPart = max(maxPart, upPart);if (maxPart < minMaxPart){minMaxPart = maxPart;centroids.clear();centroids.push_back(u);}else if (maxPart == minMaxPart){centroids.push_back(u);}
}int main()
{cin >> n;tree.resize(n + 1);//结点从1开始标记subtreeSize.resize(n + 1);for (int i = 1; i < n; i++){int u, v;cin >> u >> v;tree[u].push_back(v);tree[v].push_back(u);}dfs(1, 0); //从结点1开始dfs（任选）cout << "树的重心是：";for (int u : centroids)cout << u << " ";cout << endl << "删除后最大块大小：" << minMaxPart << endl;return 0;
}

运行结果：