0846

846. 树的重心

题目

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

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

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

输入格式

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

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

输出格式

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

数据范围

$1 \le n \le 10^5$

输入样例

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

输出样例：

4

题解

前置题目：0845

前置知识：单链表

本题知识：搜索与图论-DFS

题目分析

树的深度优先遍历

树与图的存储

树是一种特殊的图，与图的存储方式相同。 对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。

1. 邻接矩阵：g[a][b] 存储边a->b

2. 邻接表：

   const (
   	// 树的结点数
   	N = 100010
   	// 邻接表存储树，每个点都会存储两次
   	M = 2 * N
   )
   
   // 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
   var (
   	h [N]int
   	e [M]int
   	ne [M]int
   	idx int
   )
   
   // 添加一条边a->b
   func add(a int, b int) {
   	e[idx] = b
   	ne[idx] = h[a]
   	h[a] = idx
   	idx++
   }
   
   // 初始化
   func init() {
       idx = 0;
       for i := 0; i < len(h); i++ {
   		h[i] = -1
   	}
   }

树与图的遍历

时间复杂度 O(n + m), n 表示点数，m 表示边数

深度优先遍历

var st [N]bool

func dfs(u int) {
	// st[u] 表示点u已经被遍历过
	st[u] = true

	for i := h[u]; i != -1; i = ne[i] {
		j := e[i]
		if !st[j] {
			dfs(j)
		}
	}
}