树的重心（dfs深度搜索）

2023-12-22 12:52

文章标签 搜索深度 dfs 重心

本文主要是介绍树的重心（dfs深度搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

树的重心

原题链接：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;
}