链式前向星啊

链 式 前 向 星

（https://www.cnblogs.com/tushukai/p/11252522.html）此处应该提到过树的存储吧。。。。。。
但是，我今天来介绍一种NB的存图方式--链式前向星

有链式前向星 就一定有 前向星

那么，前向星的定义是：

一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.

用len[i]来记录所有以i为起点的边在数组中的存储长度.
用head[i]记录以i为边集在数组中的第一个存储位置.

那么，可不可以优化呢

可以看到，前向星主要慢在了“排序”，但他其实...... 那么，优化就来了：
把排序的步骤删掉。

事实证明，从n log n变为O(n)

好的，大家都需要的 模板

其实，另外还有一个数组head[],它是用来表示以i为起点的第一条边存储的位置,实际上你会发现这里的第一条边存储的位置其实在以i为起点的所有边的最后输入的那个编号.

struct edge{
    int v,w,next;//v是终点,w为权值,next表示与第i条边同起点的下一条边的存储位置
}e[200005];
void add(int u,int v,int w){
    e[++cnt].v=v; e[cnt].w=w;
    e[cnt].next=head[u]; head[u]=cnt;
}