稀疏图的链式前向星表示 (Sparse Graph & Chain Forward Star)

📖 算法原理：数组模拟链表与头插法

在稀疏图（边数 $E$ 远小于 $V^2$）中，使用邻接矩阵将浪费大量空间。链式前向星利用结构体数组模拟静态链表：

1. 使用一维数组 head[u] 记录以顶点 $u$ 为起点的最后一条加入的边在 edge 数组中的索引。
2. 新加入一条有向边 $u \to v$ 时，采用头插法：
• 新边节点 edge[cnt] 的 next 指针直接指向旧的 head[u]（挂接原有链表首部）。
• head[u] 的值更新为当前边的索引 cnt（head 重新定向到新节点）。
• cnt++ 递增计数。

struct Edge {
    int to;   // 有向边终点
    int w;    // 边权
    int next; // 以同起点上一条加入的边的 edge 数组索引
} edge[MAXM];

int head[MAXN]; // 记录起点 u 对应的最后一条边的索引，初始为 -1
int cnt = 0;    // 当前边计数器

void addEdge(int u, int v, int w) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u]; // 第一步：新边 next 指向当前 u 的 head 首节点
    head[u] = cnt++;          // 第二步：head[u] 偏转指向新边，cnt 递增
}