【OI题解】Acwing 846
846.1 题目描述
给定一颗树,树中包含 n 个结点(编号 1∼n)和 n−1 条无向边。
请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
846.2 题解
$\qquad$重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
$\qquad$众所不周知,图的遍历有三种方式:深度优先遍历和二进制宽度优先遍历(广度优先遍历),以及完全二叉树转换遍历(没用)
深度优先遍历:
就是一条道走到黑,不碰壁不回头
时间复杂度高于二进制宽度优先遍历,但是可减支优化,代码简单
ip17普及T3练习(CSP练习应该有),我看洛谷也有(luogu.org)
二进制宽度优先遍历(广度优先遍历):
慢慢的走,按照走的步数来排序
什么一起学的,非深度优先遍历
时间复杂度较低,但是优化很难
实际上和栈/队列的性质有关
$\qquad$这道题抠定义就能做
$\qquad$需要使用邻接表
846.3 代码实现
$\qquad$深度优先遍历求解
#include <cstdio>
#include <memory.h>
#include <iostream>
int res, ans = 100000010;
int n, m;
int E;
bool vis[1000010];
const int N = 1000010;
const int M = 1000010;
int head[N], to[M], nxt[M], idx;
int dfn[N], low[N], timestamp; // 时间戳
int stk[N], top;
int id[N], dcc_cnt; // 每个点所属分量编号
bool is_bridge[M];
using std::min;
using std::max;
void init()
{
memset(head, -1, sizeof head);
E = 0;
}
void add(int a, int b)
{
to[E] = b;
nxt[E] = head[a];
head[a] = E;
E ++;
}
int dfs(int u)
{
vis[u] = true;
int sum = 1, res = 0;
for(int i = head[u]; ~i; i = nxt[i])
{
int v = to[i];
if(! vis[v])
{
int s = dfs(v);
res = max(res, s);
sum += s;
}
}
res = max(res, n - sum);
ans = min(ans, res);
return sum;
}
int main()
{
init();
scanf("%d", &n);
for(int i = 1; i < n; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
dfs(1);
printf("%d\n", ans);
return 0;
}