图

所谓图（graph），是图论中基本的数学对象，包括一些顶点，和连接顶点的边，这里的边只是表示顶点的连接情况，用直线或曲线表示均可。图可以分为有向图和无向图，有向图中的边是有方向的，而无向图的边是双向连通的。

存图

当图为稀疏图时，更适宜选择邻接表作为存储结构。当图为稠密图时，使用邻接矩阵作为存储结构较为合适。

链式前向星

链式前向星，由Malas命名，是除了邻接表和邻接矩阵外的另一种稍稍不同的数据结构。要了解它，首先要知道什么是前向星。前向星，Forward Star，说实话在网上资料不是非常多，在外网也是如此。看了点资料，一个点的前向星是由这个点出发的边的集合。也有中文博客提到前向星存点可以用pair<int,int>G[MAXN_E]的方式，其中每个pair保存的是起始点和中止点的编号。记录好后以起点编号为第一关键字，终点编号为第二关键字升序排序。还需要两个数组，head[i]代表以i起点的边集的开始的下标，len[i]代表以i为起点的边集的大小。这样用首地址+偏移量的方式，就可以遍历图了。

我们输入边的顺序为:

2 3 
3 4 
1 3 
4 1 
1 5 
4 5

用pair存储并排序后得到

G[0]=(1,2); G[1]=(1,3); G[2]=(1,5); 
G[3]=(2,3); G[4]=(3,4); G[5]=(4,1); 
G[6]=(4,5);

则head数组和len数组为:

head[1]=0; head[2]=3; head[3]=4; head[4]=5; head[5]=-1;
len[1]=3; len[1]=3; len[3]=1; len[4]=2; len[5]=0;

而链式前向星用了以下结构：

struct node{
    int to,next,w;
}edge[maxe];

int head[maxn];//头结点数组

同样的，edge[i]表示第i条边；head[i]存以i为起点的第一条边的下标(在edge[]中的下标)，初值赋为-1。

插入的时候由于采用头插的方式，因此插入时next即为上一条边，而遍历时由于从头开始遍历，因此next确实是下一条边。即存图顺序或者说是遍历顺序是相反的。

该数据结构还有一些特性，如可以通过与1的异或运算（i^1）得到其反向边等，这里就不多说了。

#include<bits/stdc++.h>

//#define LOCAL
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'

#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int long long

const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 5;

struct {
    int to, w, next;
} edge[MAXN * 2];
int head[MAXN];
int cnt;
int n;
int x, y, m, z;

void add(int u, int v, int w) {
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

void printing() {
    for (int v = 1; v <= n; v++) {
        cout << v << "：  ";
        for (int i = head[v]; i != -1; i = edge[i].next) {
            int v1 = edge[i].to, w1 = edge[i].w;
            cout << "[" << v1 << " " << w1 << "]\t";
        }
        cout << endl;
    }
}

vector<int> path;

void dfs(int x) {
    vis[x] = 1;
    path.push_back(x);
    for (int i = head[x]; i != -1; i = edges[i].next) {
        if (!vis[edges[i].to])dfs(edges[i].to);
    }
}

void bfs(int x) {
    queue<int> q;
    q.push(x);
    vis[x] = 1;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        path.push_back(now);
        for (int i = head[now]; i != -1; i = edges[i].next) {
            if (!vis[edges[i].to]) {
                q.push(edges[i].to);
                vis[edges[i].to]=1;
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    while (m--) {
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    printing();
}