今天上午模拟赛的时候，（十分错误地）判断有一道题可以用LCA混点分（然而还不如直接爆搜得分高），在敲那个LCA的代码时突然想起来我好像还没有写过LCA，想了想，是该给我的LCA写点东西了呢。

　　但是！不出意外的，出了亿点点意外，就是我在敲板子题的时候发现经过一年的荒废，我已经完全不会链式前向星。好不容易捣鼓了半天，终于还是没调出来，于是我只能十分痛心疾首地去好好学习了一下。

　　所以！本来今天要说说LCA的，但是最终我决定还是先讲讲图论最最基础，也是最为致命（啊，就是说我因为不会链式前向星导致我没把LCA整出来）的东西之一，存图！

　　这里只介绍两种常用的方法，如有需要的的同学可以看看别人的拓展。

--------------------------------------分割线---------------------------------------------

一，邻接矩阵

　　邻接矩阵顾名思义，是一个矩阵（废话），在老一点的算法书里面常常能见到用这种方法存图的代码。优点是特别简单好理解，用起来也是非常的方便；缺点在于空间复杂度是n^2级的。

　　举个例子吧，有如下无向连通图（每边边长为1）

　　首先我们要开一个数组f[mm][mm]，其中f[i][j]表示点i到点j之间连边的长度，如下图

　　　　另外，很显然一个点到它自己的距离是零

　　因为这是一个无向图，所以存图的时候要注意f[i][j]=f[j][i]这一点，即，同一边要存两次；

　　如果说点i和点j之间没有直接的边那应该如何表示呢？很简单，初始化为inf，两个点之间距离无限远不就是说两点之间不能互相直接到达吗，所以见如下代码

二、链式前向星

　　链式前向星近些年非常常见，它的诞生让图论题的数据范围大幅提高（真是太糟糕了），相比于邻接矩阵，链式前向星确实会更复杂、更难自己想（指的是我自己调半天都不知道问题在哪），但一个标准的链式前向星的代码量其实很少，占用的空间也会少得多

　　邻接矩阵实际上是基于点的存图，它储存的是点与点之间的连边，而链式前向星是基于边的存图，它储存的是一条条的边，每条边的两个端点分起点终点。

　　我们选择使用结构体（结构体介绍：https://www.cnblogs.com/qj-Network-Box/p/13138534.html）来实现存边的操作，一条边的要素，无非是起点终点和长度，由于上图每条边的长度一样，暂时先不考虑长度的问题

　　很显然，链式前向星，身为一个用链开头的词，和链表多多少少有点联系

　　而这个联系就在于：同一起点的边被排成一条链。原因很显然，方便查询

　　我们回到这幅图

　　按照起点分类，可以变成以下几串

 　　比如，要实现查询到点1到点2的路径后能找到点1到点3的路径，就可以在存点1到点2路径的结构体里面添加一个nex元素，nex指向下一个以1为起点的元素

　　那么问题来了，我们一开始怎么找到点1到点2的那条边呢（身为该起点被存入的第一条边，没有nex指向它），我们需要一个head[x]数组来存储起点为x的第一条边的序号

　　显然既然是同一起点的，在存边的时候就不需要把起点算进去了

 　　考虑遍历，以x为起点的第一条边编号为head[x],下一条就应该是a[head[x]].nex,再下一条就是a[a[head[x]].nex].nex，直到某个节点的nex指向0

　　代码实现如下