邻接表存储图或者树

介绍

• 每个顶点都作为头节点，并且存在一个一维数组中h[N]。
• 树就是相当于一种有向图。
• 存储无向图的时候直接add(a, b), add(b, a)就行了。
• 常用于稀疏图。
  

源码

初始化

int h[N], e[N], ne[N], idx = 0;
memset(h, -1, sizeof h);

添加a到b的一条有向连接

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}