链式前向星

核心理解

head[u] 存节点 u 最新一条出边的编号；每条边的 next[i] 指向同一出发点的上一条边。新增一条边只需 O(1)，遍历 u 的所有出边时沿 next 链走即可。

• 复杂度：加边 O(1)；遍历所有边 O(m)。
• 注意：无向图要调用两次 add；数组大小要预留双倍边数。

模板代码

下面代码直接摘自你的 拓扑排序.cpp；该文件没有单独的链式前向星模板，所以这里不补写、不改名。

const int maxn=1e5;
int to[maxn],ne[maxn], h[maxn],idx,in[maxn];
void add(int a, int b)
{
	to[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
	in[b]++;
}