前言
看到这题,第一想法就是暴力求解,然而暴力解法会超时,因此参考了几位大佬的解法,冥思苦想终于理解了并顺利解决了该问题
题目分析
首先我们先来考虑这样一个问题,对于一个树状结构,当我们将上面的某一个结点删除后会形成哪些连通集呢?
显然会形成两种连通集:一种是由它的子树产生的、另一种是以它的父亲节点为根节点形成的新的子树
而这两种连通集中最大的哪一个就是删掉该结点后产生的最大连通集
利用递归思想,以某一个结点为根节点的子树大小就等于该结点所有孩子结点形成的子树大小之和再加上1,因此我们首先可以使用DFS算法计算出以每一个结点为根节点的子树的大小
int DFS(int u){
vis[u]=1;
int sum=1; //记录下以结点u为根节点的子树大小
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(vis[j]==0){
int s=DFS(j);
sum+=s;
}
}
return sum;
}
进一步的,正如我们一开始分析的那样:删掉该结点后产生的最大连通集要么是以其子结点为根节点产生的,要么是以其父亲节点为根节点产生的,而以其子结点为根节点产生的连通集大小实际就是以该子结点为根节点的子树大小,以其父亲节点为根节点产生的连通集大小实际就是总结点树减去以该结点为根节点的子树大小
因此,我们只需要对上述DFS算法再稍作修正
int DFS(int u){
vis[u]=1;
int sum=1; //记录下以结点u为根节点的子树大小
int res=0; //记录下删掉该节点之后所形成的最大的连通子图的节点数
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(vis[j]==0){
int s=DFS(j);
res=max(res,s); //此时res表示该结点u的最大子树大小
sum+=s;
}
}
res=max(res,n-sum); //n-res表示的就是去掉该结点所在子树后以其父亲节点为根节点的联通子图中元素个数
//经过比较,得到删掉节点u之后剩余各个连通块中点数的最大值
ans=min(ans,res); //与此前已经得到的删除某个点后,剩余各个连通块中点数的最大值的最小值比较,若删掉当
//前节点后得到的剩余各个连通块中点数的最大值更小,就更新它
return sum;
}
注意:这里的ans一开始要初始化为一个较大的数
算法实现
注意:该题目中是无向图,因此数组大小应开到理论最大值的两倍
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int h[N],vis[N],e[2*N],ne[2*N],idx;
int ans=N;
int n;
int DFS(int u){
vis[u]=1;
int sum=1; //记录下以结点u为根节点的子树大小
int res=0; //记录下删掉该节点之后所形成的最大的连通子图的节点数
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(vis[j]==0){
int s=DFS(j);
res=max(res,s); //找到该结点的最大子树
sum+=s;
}
}
res=max(res,n-sum); //n-res表示的就是去掉该结点所在子树后以其父亲节点为根节点的联通子图中元素个数
//cout<<u<<" "<<res<<endl;
ans=min(ans,res); //看删掉哪一个结点剩余各个连通块中点数的最大值最小
return sum;
}
void insert(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
int main(){
cin>>n;
fill(h,h+n+1,-1);
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
insert(a,b);
insert(b,a);
}
DFS(1);
cout<<ans<<endl;
return 0;
}