树和图的存储

1.稠密图（邻接矩阵）
用二维数组g[N][N]，如a -> b, 即g[a][b] = 1；

2.稀疏图（邻接表）
用链表存储

模板

const int N = 100010, M = 2 * M;
int h[N]; //头结点
int e[M]; //节点编号
int ne[M]; //指向下个节点的指针（next）
int w[M];  //如果是带边权的，那么存储每条边的边权
int idx;  //节点编号

void add(int a, int b, int c)  //在头结点为a的链表后插入一个节点b，边权为c
{
    e[idx] = b;  //开辟一个空间，存放a -> b这条边
    w[idx] = c;  //给这条边赋值
    ne[idx] = h[a]; //将头结点的ne指针赋给b的ne指针
    h[a] = idx ++; //将该节点编号（指针）赋给头结点的ne，然后节点编号自加
}

int main(){
    for (int i = 1; i <= n; i ++) //n为节点数
        h[i] = -1; //头结点的ne指针全初始化为-1
        
}