树的重心（DFS）

2023-05-21 14:51| 来源: 网络整理| 查看: 265

题目

给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数 n，表示树的结点数。

接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式

输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

1≤n≤10^5

输入样例

9 1 2 1 7 1 4 2 8 2 5 4 3 3 9 4 6

输出样例：

题解 #include #include #include #include using namespace std; const int N = 1e5 + 10;//点数 const int M = N * 2;//边数为点数的两倍 int n;//输入的点数 int h[N], e[M], ne[M], idx;//老四件 bool st[N];//做访问标记 int ans = N;//答案 void add(int a, int b){//单向连通边a->b e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } int dfs(int u){ st[u] = true;//标记已访问 int size = 0, sum = 0; //size记录子连通块中最大的点数,sum统计当前点共有多少子点 for(int i = h[u]; i != -1; i = ne[i]){ int j = e[i]; if(st[j])continue;//访问过，跳出 int s = dfs(j);//继续深搜 size = max(size, s); sum += s;//统计 } size = max(size, n - sum - 1);//n-sum-1是当前节点的父点统计 ans = min(size, ans);//找符合要求的结果 return sum + 1; } int main(){ cin >> n; memset(h, -1, sizeof h);//初始化！！！ int a, b; for(int i = 1; i > a >> b; add(a, b); add(b, a); } dfs(1); cout

【本文地址】

公司简介

联系我们