树的重心(dfs深度搜索)

发布时间:2023年12月22日

树的重心

原题链接:846. 树的重心 - AcWing题库

邻接表存储树图 模板代码

void add(int a, int b){
    e[id] = b,ne[id] = h[a], h[a] = id++;
}

dfs 搜索树 模板代码

void dfs(int u){
    f[u] = true;
    for(int i = h[u]; i!=-1; i = ne[i]){
        int j = e[i];
        if(!f[j])dfs(j);
    }
}

整体思路 :本质上就是使树尽可能的散碎,从一个点开始,直接低轨道到最低点,然后开始回溯,回溯的过程中计算各个连通块的中点的数量,因为每个结点都会存在有一条链没有被遍历,所以我们可以通过n-sum 得到那条链的结点的数目

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int h[N],ne[N*2],e[N*2],id;
bool f[N*2];
int ans = N;
int n;
void add(int a,int b){
    //e中存储的是下一个边是哪条边
    //ne存的是当前点的下一个点的序号,是一个编号
    //e[ne[i]得到的就是下一个点
    //采用的是头插法
    
    e[id] = b,ne[id] = h[a],h[a] = id++;
}
//答案要找的是 当前连通块中,最大的连通块的节点个数最小。本质上就是使树尽可能的分散
//思路就是,遍历每一个结点,找到去除这个结点后
//每一个联通块的最大值,最后在所有的最大值中输出最小的值,也就是最大值最小
int dfs(int u){
    int sum = 1, res  = 0;
     f[u] = true;
    for(int i = h[u];i!=-1;i = ne[i]){
        int j = e[i];
        if(!f[j]){
            //s会一路递归到最底层,直到最底层开始返回
            int s = dfs(j);//返回的就是当前结点的数目
           
            //因为s是返回的上次的sum,所以实际上是不会包含当前结点,所以达到了删除这个结点的效果
            res = max(res,s);//res记录的是删掉这点这个结点后,所有的联通块中,结点最多的连通块的结点数目
            sum+=s;
        }
    }
    //sum现在是包含着当前结点的
    res = max(res,n-sum);
    ans = min(ans,res);
    return sum;
}
int main(){
    cin>>n;
    int a,b;
    memset(h,-1,sizeof h);
    while(cin>>a>>b){
        add(a,b);
        add(b,a);
        
    }
   dfs(1);
    cout<<ans<<endl;
    return 0;
}
文章来源:https://blog.csdn.net/m0_74036487/article/details/135150189
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。