今天上午模拟赛的时候，（十分错误地）判断有一道题可以用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，两个点之间距离无限远不就是说两点之间不能互相直接到达吗，所以见如下代码

1 #include 2 using namespace std; 3 const int mm=205;//并没有什么特殊意义 4 const int inf=1e9+7; 5 int f[mm][mm]; 6 int n,m;//有n个点，m条边  7 int main() 8 { 9     cin>>n>>m;10     for(int i=1;i<=n;i++)11     for(int j=1;j<=n;j++)12     {13         f[i][j]=inf;//初始化为任意两点之间距离为inf 14      } 15     for(int i=1;i<=m;i++)16     {17         int x,y;18         cin>>x>>y;//将两个点相连 19         f[x][y]=1;20         f[y][x]=1;21      } 22     return 0;23 }

二、链式前向星

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

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

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

1 const int mm=205;//没有什么特别的意义 2 struct node{3     int s,v;//从点s到点v 4 }a[mm];

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

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

我们回到这幅图

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

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

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

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

const int mm=205;//没有什么特别的意义 struct node{    int v,nex;}a[mm*2];int head[mm];//用于储存最头部边的序号 

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

代码实现如下

#includeusing namespace std;int tot;int n; const int mm=205;//没有什么特别的意义 struct node{    int v,nex;//从点x到点v }a[mm*2];int head[mm];//用于储存第一条边的序号 void add(int x,int y) //一条x到y的边{    a[++tot].v=y;//目标是y    a[tot].nex=head[x];//将上一条边的nex指向这一条边    head[x]=tot;//更新 } void pp(int x){    for(int i=head[x];i!=0;i=a[i].nex)//以head[x]为第一边，每次跳转到nex所指的下一条边     {        cout<>n;    for(int i=1;i<=n;i++)    {        int x,y;        cin>>x>>y;        add(x,y),add(y,x);//无向图要存两边     }    for(int i=1;i<=n;i++)//输出所有的边     {        pp(i);    }    return 0;}

关键词：