一种非常厉害的存图的数据结构！
本质：模拟链表的操作，链式存储图。（2，3都可以模拟链表的操作，替代链表）
（1）二维数组存图：Map[x][y]，一维代表出发点，二维代表它所连接的所有点。（不连接设为inf）
（2）链式前向星存图：head[x]相当于一维代表了出发点，之后T[i].next一条链相当于二维代表了所有（与它）连接的点。（不连接的到0就停止了）。
如head[x]，T[head[x]].to，T[head[x]].w，T[head[x]].next，完美表示了一条边的两端点，权值，甚至下一条边存储位置序号。
所以说，二维数组存图很浪费空间（有的题目要求大也存不下），有的点之间没有连接就不用存（我们也不用），但二维数组把没链接的点之间也存下来了并且设为inf。
但链式前向星相当于链表，与某个点连接的所有点存下来形成一条链，有多少存多少，没有的就不存，节省了空间。（至于邻接链表就不说了，不直观操作不方便）
好，经过了链式前向星存图原理的诱导！明白了关键之处是：head[x]一维代表了出发点，之后一条链相当于二维代表了所有（与它）连接的点！
既然如此我们完全可以用vector代替链式前向星，因为vector更好理解看起来更直观！（本质：也相当于一条链，必须一个一个尾插入pushback，这就是链表啊！）
（3）vector链式顺序存图：vec[x][i]，x即一维代表了出发点，[i]即二维代表了所有与x相连相关的点的信息依次链式顺序存放，成一条链。
注意：vector容器里面什么都可以塞，各种信息都存放的下，又相当于一个结构体。所以存图，对付空间问题，链式之类的最好用vector，一般都能解决。（虽然不一定比前向星快，但是操作方便，理解直观啊！）
更新实测：数据小量或一般的时候没什么，但大量或极端时，链式前向星比vector快！洛谷P4779，前向星比vector快了200ms左右！
一般情况下先vector好理解，一般够用了，不行了再换链式前向星！
前向星
1 int head[maxn];//每个顶点(从i出发)的第一条边(相当于头指针,指向首元结点) 2 struct px 3 { 4 int next; 5 int to; 6 int w; 7 }T[maxm*3];//注意T存的是所有边数(边的连接信息,终点,权值,下条边都在这里),无向图是2倍 8 9 10 void Add(int x,int y,int z)//加边操作 11 { 12 T[++cnt].next=head[x];//相当于链表前插法,新结点指向了头指针指的结点 13 T[cnt].to=y; 14 T[cnt].w=z; 15 head[x]=cnt;//前插完成,头指针已经指向了新结点 16 } 17 18 19 for(int i=head[x];i;i=T[i].next)//遍历(与某个点x连接的所有边和点) 20 { 21 cout<<x<<' '<<T[i].to<<endl;//输出这条边的两个端点(x一直是一端,存的就是所有与它连接的点) 22 cout<<T[i].w<<endl;//输出这条边的权值 23 24 }
vector改进
1 struct px 2 { 3 //int next; 4 int to; 5 int w; 6 }T; 7 vector<px> vec[maxn]; 8 9 vec[x].push_back(T);//加边操作 10 11 for(int i=0;i<vec[x].size();i++)//遍历(与某个点x连接的所有边和点) 12 { 13 int J=vec[x][i].to,W=vec[x][i].w; 14 cout<<x<<' '<<J<<endl;//输出这条边的两个端点(x一直是一端,存的就是所有与它连接的点) 15 cout<<W<<endl;//输出这条边的权值 16 17 }
可以看到，用了vector存图无论是加边，遍历都方便直观了许多！
完。