因为需极致常数性能，vector的动态扩容、迭代器失效和内存不连续会拖慢遍历；数组模拟邻接表（链式前向星）通过head[]、to[]、next[]实现连续内存访问与零函数调用开销。
为什么不用 vector 而用数组实现邻接表
因为需要极致的常数性能（比如 OI 高频图题），vector 的动态扩容、迭代器失效、内存不连续都会拖慢遍历；而静态数组配合链式前向星（即“数组模拟邻接表”）能保证所有边访问都是连续内存跳转，且无函数调用开销。
核心思路是：用两个全局数组 head[] 存每个点的“第一条边编号”，用 to[] 和 next[] 模拟单链表。每加一条边 u → v，就往数组末尾塞一个新节点，并更新 next[new_idx] = head[u]，再令 head[u] = new_idx。
关键数组定义和初始化怎么写
假设最多 N 个点、M 条边（有向），需提前开足够大的静态数组：
const int N = 1e5 + 5; const int M = 2e5 + 5; // 注意：无向图边数×2 int head[N], to[M], next[M], idx; // 初始化：memset(head, -1, sizeof head) 或 for(int i = 1; i <= N; ++i) head[i] = -1; // idx 初始为 0，每次 add_edge 后自增
注意三点：
立即学习“C++免费学习笔记（深入）”；
-
head[]初始必须为-1，表示空链表；不能用0，否则和合法下标混淆 -
idx从0开始，所以next[]数组下标范围是[0, M-1] - 无向图要调用两次
add_edge(u, v)和add_edge(v, u)，别漏
add_edge 和遍历邻接表的写法
添加边就是头插法，保持插入顺序不影响正确性，但会影响遍历顺序（后加的边先被访问）：
void add_edge(int u, int v) {
to[idx] = v;
next[idx] = head[u];
head[u] = idx++;
}
遍历点 u 的所有出边：
for (int i = head[u]; i != -1; i = next[i]) {
int v = to[i]; // u → v 是一条边
// ... 处理逻辑
}
常见错误：
- 循环条件写成
i —— 错，<code>idx是总边数，但head[u]链只含部分下标 - 忘记在
add_edge里更新idx++，导致所有边都堆在to[0]/next[0] - 把
to[i]误当成点编号而非目标点，尤其在重边/自环场景下容易逻辑错
空间和索引边界容易踩的坑
数组大小不是拍脑袋定的：
- 若题目说
n ≤ 10^5，边数m ≤ 2×10^5，那M至少设为200005，建议上浮 5% 避免 RE -
head[]下标是点编号，所以大小看点数上限，不是边数 - 多组数据时，
idx必须清零，head[]必须重置为-1；只清idx=0不清head[]会残留旧图指针 - 如果用结构体封装（如
struct Edge { int to, next; } e[M];），则head[u]存的是结构体下标，逻辑一致，但可读性略高
最常被忽略的是：当点编号从 0 开始时，head 数组大小仍要开到 N，且初始化范围得覆盖 [0, N-1]，否则访问 head[n-1] 可能越界。
