C++树形DP基础—————求树的重心
题目描述:
树的重心定义为树的某个节点,当去掉该节点后,树的各个连通分量中,节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图(自制),当去掉点1后,树将分成两个连通块:(2,4,5),(3,6,7),则最大的连通块包含节点个数为3。若去掉点2,则树将分成3个部分,(4),(5),(1,3,6,7)最大的连通块包含4个节点;第一种方法可以得到更小的最大联通分量。可以发现,其他方案不可能得到比3更小的值了。所以,点1是树的重心。
输入:
输入:第一行一个整数n,表示树的结点个数。(n<100)
接下来n-1行,每行两个数i,j。表示i和j有边相连。
输出:
输出:第一行一个整数k,表示重心的个数。
接下来K行,每行一个整数,表示重心。按从小到大的顺序给出。
样例输入:
7
1 2
1 3
2 4
2 5
3 6
3 7
样例输出:
1
1
思路分析:
其实这一题不同于其它的树形DP,这一题是先DFS,再DP(之前都是树形与DP一步到位)。
所谓重心,就是去掉此点与它相连的边之后,图中所存在的子树中的节点数最大的值的最小值。
是不是感觉有点懵?
没事,我们可以这样想。
设p[i]为去掉i点与它相连的边之后,图中所存在的子树中的节点数最大的值。
将p数组比较,最小的就是树的重心。
好了,理解了题目,我们开始解题。
思考一下,再去掉点后,它的儿子就会各自为营独立成为子数,节点数就是儿子加1(它本身)。
还有一棵由原根节点为根的树,它的节点数就是原树-(被取点的儿子树+1)。
再逐一比较,最大的就是p[i]了。(最后有彩蛋)
代码实现:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int n,m,son[105],ans,id[105],len,p[105],lenp;
vector<int>G[105];
bool v[105];
int dfs(int x)
{
if(!G[x].size())
return 1;
int sum=0;
for(int i=0;i<G[x].size();i++)
{
if(!v[G[x][i]])
{
v[G[x][i]]=1;
sum+=dfs(G[x][i]);
}
}
return sum+1;
}
int main()
{
scanf("%d",&n);
int a,b;
for(int i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
G[a].push_back(b);
}
for(int i=1;i<=n;i++)
{
memset(v,0,sizeof(v));
v[i]=1;
son[i]=dfs(i);
}
int minn=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
int maxn=n-son[i];
for(int j=0;j<G[i].size();j++)
maxn=max(maxn,son[G[i][j]]);
minn=min(maxn,minn);
p[i]=maxn;
}
for(int i=1;i<=n;i++)
{
if(p[i]==minn)
{
lenp++;
id[lenp]=i;
}
}
printf("%d\n",lenp);
for(int i=1;i<=lenp;i++)
printf("%d\n",id[i]);
}
画图网站:https://csacademy.com/app/graph_editor/