图的储存

链式前向星

const int maxn = 1e5+10;
struct edge {
    int to;
    int nxt;
};
edge e[maxn * 2];//无向图开双向边
int h[maxn],tot = 1;
void addeage(int x, int y) {
    e[++tot].to = y;
    e[tot].nxt = h[x];
    h[x] = tot;
}
void solve(int i) {
    //……
    for (int x = h[i]; x; x= e[x].nxt) {
        solve(e[x].to);
    }
    //……
}

邻接表

无向图开双向边

const int MAXN = 1e5 + 10;
//结构体里定义的是该边的终点和边权；
struct edge {int to, cost;};
vector<edge> g[MAXN];
//加边
//from：起点，to：终点，cost：边权
void addedge(int from, int to, int cost) {
g[from].push_back(edge{to, cost});
}
//若为无权图可以直接这么写
vector<int> g[MAXN];
//若有一条从i指向j的边
g[i].push_back(j);
​