穿越隧道
DFS
【acwing|【acwing】846. 树的重心**】题意:删掉树中的一个点（及该点的所有边）。
剩下的连通块中，每个联通块中的结点数是多少。
题意要求连不同通块中点的数量的最大值 里面的最小值。
#include
using namespace std;
const int N = 1e6 + 10;
//1e5 + 10,会wa;
可能数据量变大了
int h[N],e[N],ne[N],idx;
int n;
int ans = N;
//要找最小的ans,此时给ans赋予一个本题最大的值。
void add(int a,int b){
e[idx] = b, ne[idx] = h[a],h[a] = idx++;
}
bool st[N];
int dfs(int u){//算以u为根节点的子树中点的数量
int sum = 1, res = 0;
//
st[u] = true;
//访问过的点就不再访问了
for(int i = h[u];
i != -1;
i = ne[i]){
int j = e[i];
if(!st[j]){
int s = dfs(j);
//s是以j为根节点中子树结点的数量
res = max(res,s);
//找连通块的子树结点最多的值
sum += s;
//j同样为是u的子树
}
}
res = max(res, n - sum);
//和另外的连通块比较
ans = min(ans,res);
return sum;
}
int main(){
cin >> n;
memset(h,-1,sizeof(h));
for(int i = 0;
i < n - 1;
i ++){
int a,b;
cin >> a >> b;
add(a,b);
add(b,a);
}
dfs(1);
//随便从哪个点开始搜
cout << ans << endl;
return 0;
}
推荐阅读
- 每天刷题档|merge_sort_归并排序 —每日算法档
- 算法笔记练习题|(5.6B)n的阶乘
- 蓝桥杯Java真题|19年蓝桥杯Java B组省赛第三题（数列求值）
- 华师oj|2857. 编辑距离
- 13届蓝桥杯夺奖冲刺营|蓝桥杯省赛夺奖冲刺营链表篇
- 数据结构|最新|蓝桥杯备赛冲刺攻略，人手必备！
- 数据结构与算法学习|数据结构与算法作业8（排序算法的应用）
- matlab机械臂工作空间代码|matlab机械臂工作空间代码_【ROS-Moveit!】机械臂控制探索（3）——基于python的API示例代码分析...
- opencv|opencv学习笔记（二） 图像腐蚀和膨胀