链式前向星

一句话理解

链式前向星是数组模拟的邻接表。

为什么要学

快、省、支持边编号。

讲解

e[i] 存终点，ne[i] 存下一条边，h[u] 是头。加边 O(1)。

例子

void add(int u, int v, int w) {
    e[++idx] = v; wgt[idx] = w;
    ne[idx] = h[u]; h[u] = idx;
}

遍历 for(int i=h[u]; i; i=ne[i])。

常见错误

• idx 从 0 且 h 初始 0 分不清。常用 idx=1 或 ~0。
• 无向边编号成对。