vector存图

vector存图是一种非常优秀的存图技巧

其适用面也是非常的广泛，基本所有的图论题都可以用vector存图

首先来讲一讲vector

vector是一种数据结构

它可以说是一种长数组类型

普通的数组一般是一个点存一个数

但是vector类型数组可以一个点存很多个数

基于这一点，可以将图中点与点之间的关系放到一个vector数组中去

比如：a与b，c，d有边

那么用vector数组d[i]来存就是：

d[a] = {b,c,d};

这样边的关系就出来了

另外vector数组需要注意的几个地方：

• 必须使用

using namespace std //标准数据库

• 存入指令

push_back()

• 求长度

size()

• 清除

erase()

• 申请一个vector数组

vector </*一般整型或结构体*/> /*名字*/

代码实现：

#include <bits/stdc++.h>

using namespace std;//标准数据库 

int start;//开始点 

int n, m;//点的数量，边的数量 

struct node {
	int to;//终止点 
	int cost;//边的大小，即权值 
};

vector <node> k[100001];//申请一个vector数组 

int main() {
	cin >> n >> m;
	for(int i = 1; i <= m; i ++) {
		node e;//e为node类型的结构体 
		cin >> start >> e.to >> e.cost;//输入开始点，终止点，权值 
		k[start].push_back(e);//将开始点，终止点存入vector数组k 
	}
	for(int i = 1; i <= n; i ++) {//遍历图，就是把图走一遍 
		for(int j = 0; j < k[i].size(); j ++) {//记住vector的起始位置一定是0 
			node r = k[i][j];//将i点的终止点，权值赋值给r结构体 
			cout << "start: " << i << "to: " << r.to << "cost: " << r.cost << endl;//输出测试 
		}
	}
	return 0;
}