邻接表

核心理解

邻接表只保存真实存在的边。graph[u] 就是从 u 出发能走到的所有点；树的 DFS、BFS、LCA、拓扑排序都常以它为基础。

• 空间复杂度：O(n + m)。
• 适合：稀疏图和普通竞赛题。
• 注意：无向边要双向加入；带权图可以把 int 改为 pair<int, int>。

模板代码

下面代码直接摘自你的 最近公共祖先（LCA）.cpp；它是模板中实际使用的邻接表部分。

vector<int>g[maxn];

for (int i=1;i<n;i++)
{
	int a,b;
	cin>>a>>b;
	g[a].push_back(b);
	g[b].push_back(a);
}