链式前向星

如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好写，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。 ——摘自《百度百科》
————————————————————————————————————————————————

由于本人 ~~不会写~~ 懒得写邻接表，因此在做题时大量使用链式前向星，在这里放一个自己的模板。
注释：head数组存放的是与每个节点相连的第一条边的编号；cnt是边的编号，初始值自定；a是存放边的数组；结构体edge中to是边连接的下一个节点，nxt是与这条边同一个起始节点的下一条边的编号，w是权值；add_edge函数是头插法。

//链式前向星
const int MAXN=1e6+7;
int head[MAXN];
int cnt=0;
struct edge{
	int to , nxt , w;
};
edge a[MAXN];
void add_edge(int u , int v , int w) {
	a[cnt].w = w;
	a[cnt].to = v;
	a[cnt].nxt = head[u];
	head[u] = cnt ++;
}

遍历函数是这样的：

for(int i = 1; i <= n; i++)//n个起点
    {
        cout << i << endl;
        for(int j = head[i]; j != -1; j = edge[j].nxt)//遍历以i为起点的边
        {
            cout << i << " " << edge[j].to << " " << edge[j].w << endl;
        }
        cout << endl;
    }