链式前向星

由链式前向星版本的dfs引入链式前向星：

void dfs(int u,int pre){
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==pre) continue;
        dfs(v,u);
    }
    cout<<u<<" ";
}

for函数结构

1. init: i=head[u]
2. condition: i (i!=0)
3. increment: i=edge[i].nxt

结合循环中v=edge[i].to 可知：

• head[u]存储的是这个节点第一条边的编号
• i遍历边的编号
• edge[i].nxt存储下一条边的编号

这就构成了一个以边为节点的链表，head[u]与edge[i].nxt分别是链表头与指向链表下一个元素的指针。

容易得出加边函数的定义与边结构体的定义：

const int maxm=1e5+5;
struct Edge{
    int nxt,to,w;
}edge[maxm];
int head[maxm],tot=0;
void add_edge(int u,int v,int w){
    edge[++tot].nxt=head[u];
    edge[tot].to=v;
    edge[tot].w=w;
    head[u]=tot;
}

空间复杂度O(m)，edge[++tot]可以像常规邻接表实现那样使用vector<Edge> edge;只不过常数略大。
特殊用途：存无向图时一条边拆分成两条互为反边的有向边，这两条边在edge数组里相邻。i^1即为反边的编号。