链式前向星模板

建稠密图可以用邻接矩阵，但稀疏图再用邻接矩阵就很浪费空间了，有可能会爆空间复杂度。

可以用邻接表来实现邻接表建图，两种方法：1.链表 2.链式前向行

只讲第二种，比较常用简洁

链式前向星模板

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647#define int long long
//#include <bits/stdc++.h>
typedef long long ll;
#include<iostream>
using namespace std;const int N = 1e6 + 10;
//long long MAX(long long a, long long b) { return a < b ? b : a; }struct Edge {//当前边u->vint to, w, next;//to:边的终点//w:边的权重//next:以当前边的起点(u)的上一条存的边的编号//例如：上一条边4->6（编号是5），当前边是4->8，那么next就存的是5}edge[N];
int head[N];
//head[i]存的是以i为起点，最后所读的边的编号
//例如：i = 3，依次存有 3->4(编号为4)，3->8(编号为5)，3->10(编号为9)
//那么head[i] = 9。至于该怎么访问前两条边，就要利用edge[9].next来依次向前访问int cnt = 0;//记录当前插入了多少条边
void add(int u, int v, int w) {cnt++;edge[cnt].to = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt;
}void visit(int u) {//遍历以u为起点，能到达的邻接边for (int i = head[u]; i != 0; i = edge[i].next) {//i代表访问的编号cout << u << " -> " << edge[i].to << " = " << edge[i].w << endl;}
}signed main() {int n, m; cin >> n >> m;while (m--) {int a, b, c; cin >> a >> b >> c;add(a, b, c);add(b, a, c);}visit(1);return 0;
}

5 7
1 2 6
1 4 8
1 5 9
1 3 7
2 4 4
3 5 5
4 5 2