描述较抽象，以题目为例展示邻接表存图的用法，题目传送门

# 题目背景

# 题目大意

给定一颗树，树中包含 $n$ 个结点（编号 $1 \to n$ ）和 $n−1$ 条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

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

# 输入格式

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

# 输出格式

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

# 数据范围

$1 \le n \le 10^5$

# 解题代码

c++

#include<iostream>
#include<cstring>	 
using namespace std;
const int N = 1e5 + 10, M = N * 2;
// 无向图，邻接表指针 2 * ( n - 1 ) 
int n;
int h[N], e[N], ne[M], idx, ans = N;
// h[]存各个邻接表的头节点
// e[], ne[], idx同单链表 
bool st[N];
// st[]标记当前节点是否已经访问
// 作用：使遍历不走回头路，防止子节点搜索父节点 
// head, e[M], ne[M], idx 

void add(int a, int b)
// 头插法 
// e记录当前点的值，ne记录下一点的地址
// h记录指向的第一个点的地址
// idx记录当前用到了哪个点的下标 
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx;
	idx++;
}

int dfs(int u)
// 返回以u为根的树中所有节点个数（存在变量sum中） 
{
	int res = 0, sum = 1;
	// res储存当前连通块中节点的最大数目 
	st[u] = true;
	// 走过的点更新为true 
	for(int i = h[u]; i != -1; i = ne[i])
	// 从 u 为表头的链表开始遍历，中间递归走分支，直到 u 的链表尾结束 
	{
		int j = e[i];
		if(!st[j])	// 走到没有走过的点时，走它的分支 
		{
			int s = dfs(j);	// s 存储各个分支的节点数 
			res = max(res, s);
			// 找出删除u后u子树中最大连通块的节点个数 
			sum += s;
			// 以u为根节点的树节点数量 = 1 + 各个子树节点数量 
		}
	}
	res = max(res, n - sum);
	// 比较删除u后u子树中最大连通块，和整个树减u字数剩下的连通块 
	ans = min(res, ans);
	// 在所有最大的连通块节点数目中找到最小值 
	return sum;
	// 返回以u为根的子树节点的个数 
}

int main()
{
	memset(h, -1, sizeof(h));
	// 将h[]数组全部初始化为 -1 
	cin >> n;
	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;
}

图论