Content #
链式前向星有如下两种存储结构。 1）边集数组：edge[]，edge[i]表示第i条边。 2）头节点数组：head[]，head[i]存储以i为起点的第1条边的下标（edge[]中的下标）。
struct node {
int to, next, w;
} edge[maxe]; //边集数组，对边数一般要设置比maxn*maxn更大的数
int head[maxn]; //头节点数组
对于无向图，每输入一条边，都需要添加两条边，互为反向边。这两条边互为反向边，它们在edge中的下标是相信的，因此，可以通过与1的异或运算得到其反向边，0^1=1，1^1=0。也就是说，如果一条边的下标为i，则其反向边的下标为i^1。这个特性在网络流中应用起来非常方便。
添加一条边的代码如下：
void add(int u, int v, int w) {
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}
其中cnt为edge数组中的当前下标。
edge[cnt].next = head[u];
这行代码表明，新的边会添加到链表的头部。
访问节点u的所有邻接点代码如下：
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
int w = edge[i].w;
...
}
From #
《算法训练营入门篇》 陈小玉
Links #
P3916